题目描述

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note:
Rotation is not allowed.

样例

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3 
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

题意：给一堆信封，如果一个信封的长度和高度比另一个信封都要小，则这个信封能够装到另一个信封中。求问最多能选多少个信封，使得能够相互嵌套。

算法1

(dp) $O(n^2)$

题意：给一堆信封，如果一个信封的长度和高度比另一个信封都要小，则这个信封能够装到另一个信封中。求问最多能选多少个信封，使得能够相互嵌套。

题解1：这题最直观的想法就是先按照长度从小到大排序，然后变成一个类似与最长上升子序列的问题。

使用$dp[i]$来记录以第i个信封为结尾的最多信封个数。时间复杂度为$O(n^2)$

$dp[i] = max\{dp[j] + 1\},0 \leq j < i ，height[i] > height[j],width[i] > width[j]$

C++ 代码

    static bool cmp(vector<int> &A,vector<int> &B)
    {
        return A[0] < B[0];
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        if(n == 0) return 0;
        sort(envelopes.begin(),envelopes.end(),cmp);
        vector<int> dp(n,1);
        int res = 1;
        for(int i = 1 ; i < n ; i ++)
        {
            for(int j = 0 ; j < i ; j ++)
            {
                if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1])
                    dp[i] = max(dp[i],dp[j] + 1);
            }
            res = max(res,dp[i]);
        }
        return res;
    }

算法2

(暴力枚举) $O(n^2)$

题解2：注意到LIS（最长递增子序列）有$O(nlogn)$的做法，我们这一题是否也存在这样的做法呢？答案是显然的，我们在排序的时候除了按照长度从小到大排序，如果两个信封长度相同，那么按照高度从大到小排序。这样问题就转化成一个求一个以信封高度的最长递增子序列。首先$height[i] > height[j],i>j$，肯定有$width[i] > width[j]$，信封$j$可以放进信封$i$。对于长度相同的两个信封，由于高度最高的在最前面，那么长度相同的两个信封不会出现在同一个最长递增子序列当中，这也保证了最长递增子序列的每一个高度都来自与长度递增的信封。

为了更好的理解$O(nlogn)$的做法，我在这里模拟一下最长递增子序列的$O(nlogn)$做法。

假设我们有个数组d[9] = 2 1 5 3 6 4 8 9 7
新开个数组dp[9]，dp[i]存储的是所有长度为i的递增子序列的末尾元素最小值。(为了方便，下标从1开始)
cur_num = 2
dp = [2] 当前所有长度为1的递增子序列末尾元素最小值为2
cur_num = 1
dp = [1] 当前所有长度为1的递增子序列末尾元素最小值为1
cur_num = 5
dp = [1,5] 当前所有长度为1的递增子序列末尾元素最小值为1，当前所有长度为2的递增子序列末尾元素最小值为5
cur_num = 3
dp = [1,3] 当前所有长度为1的递增子序列末尾元素最小值为1，当前所有长度为2的递增子序列末尾元素最小值为3
cur_num = 6
dp = [1,3,6] 当前所有长度为2的递增子序列末尾元素最小值为3,当前所有长度为3的递增子序列末尾元素最小值为6
cur_num = 4
dp = [1,3,4] 当前所有长度为2的递增子序列末尾元素最小值为3,当前所有长度为3的递增子序列末尾元素最小值为4
cur_num = 8
dp = [1,3,4,8] 当前所有长度为3的递增子序列末尾最小值为4,当前所有长度为4的递增子序列末尾元素最小值为8
cur_num = 9
dp = [1,3,4,8,9] 当前所有长度为4的递增子序列末尾最小值为8,当前所有长度为5的递增子序列末尾元素最小值为9
cur_num = 7
dp = [1,3,4,7,9] 当前所有长度为4的递增子序列末尾最小值为7,当前所有长度为5的递增子序列末尾元素最小值为9

可以看到dp[i]数组永远是递增的，而且每次我们读到一个元素，将这个元素代替数组中第一个大于这个元素的数，如果这个元素比数组中所有元素都要大的话，那么我们就将这个元素插入队尾。查找大于这个元素的最小值，我们就可以使用二分查找来做。如果希望保存最长序列的话，可以使用$f(i,j)$来保存读到第$i$个元素长度为$j$的最长递增子数组的最小末尾元素，方便回溯。

C++ 代码

    static bool cmp(vector<int> &A,vector<int> &B)
    {
        return (A[0] == B[0])?A[1] > B[1] : A[0] < B[0];
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        if(n == 0) return 0;
        sort(envelopes.begin(),envelopes.end(),cmp);
        vector<int> dp;//dp[i]存储的是长度为i的最长递增子序列的第i个元素(这个元素越靠前越好)
        for(int i = 0 ; i < n ; i ++)
        {
            int left = 0, right = dp.size();
            int temp = envelopes[i][1];
            //找到递增子序列末尾元素小于当前信封长度的最大长度。
            while(left < right){
                int mid = (left + right) / 2;
                if(dp[mid] >= temp)
                    right = mid;
                else
                    left = mid + 1;
            }
         //如果所有当前所有递增子序列的末尾元素都小于当前信封高度，说明找到了一个新的更长的递增子序列。
            if(right == dp.size())
                dp.push_back(temp);
            else
                dp[right] = temp;
        }
        return dp.size();
    }

• 写在最后，如果信封可以旋转的话，应该怎么做，我没有想到一个很好的思路，欢迎大家交流