354. 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

 
示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

本题和面试题 17.08. 马戏团人塔一样是最长递增子序列的二维模式

我们可以对第一维进度升序的排序，然后对第一维相等的数进行降序的排序，这样就可以不管第一维，直接进行第二维的最长递增子序列求解。

先看个例子，假如排序的结果是下面这样：

[[2, 3], [5, 4], [6, 5], [6, 7]]
如果我们只看第二个维度 [3, 4, 5, 7][3,4,5,7]，会得出最长递增子序列的长度是 4 的结论。实际上，由于第 3 和第 4 个信封的第一个维度都是 6，导致他们不能套娃。所以，利用第一个维度递增，第二个维度递减的顺序排序，会得到下面的结果：

[[2, 3], [5, 4], [6, 7], [6, 5]]
这个时候，只看第二个维度 [3, 4, 7, 5][3,4,7,5]，就会得到最长递增子序列的长度是 3 的正确结果。

主要有底下两种解法，一种是动态规划，还一种是贪心+二分

class Solution {
public:
　　// 动态规划
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        int num = height.size();
        vector<vector<int>> temp(num);
        vector<int> dp(num,1);
        int maxnum = 1;
        for(int i = 0; i < num; i++){
            temp[i] = {height[i],weight[i]};
        }
        sort(temp.begin(),temp.end(),[](vector<int> &temp1, vector<int> &temp2){
            return temp1[0] < temp2[0] || temp1[0] == temp2[0] && temp1[1] > temp2[1];
        });
        for(int i = 0; i < num; i++){
            for(int j = 0; j < i; j++){
                if(temp[j][1] < temp[i][1]){
                    dp[i] = max(dp[i],dp[j] + 1);
                    maxnum = max(maxnum,dp[i]);
                }
            }
        }
        return maxnum;
    }
};

 

 

class Solution {
public: 
    /* 
        先按宽从小到大排序，但是同一个宽度的按高度从大到小排序，然后高度就按最长子序列这种题型来做(贪心 + 二分)。
    */
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end(),[](vector<int> &x1, vector<int> &x2){
            return x1[0] < x2[0] || (x1[0] == x2[0] && x1[1] > x2[1]); 
        });
        int length = envelopes.size();
        vector<int> tail;
        int maxnum = 1;
        tail.push_back(envelopes[0][1]);
        for(int i = 0; i < length; i++){
            if(envelopes[i][1] > tail.back()){
                tail.push_back(envelopes[i][1]);
            }
            else{
                vector<int> ::iterator iter = lower_bound(tail.begin(),tail.end(),envelopes[i][1]);
                *iter = envelopes[i][1];
            }
        }
        return tail.size();
    }
};