俄罗斯套娃信封问题

354. 俄罗斯套娃信封问题

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

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

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

注意：不允许旋转信封。

示例：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]

输出：3

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

思路：

我们首先想到的肯定是排序，假设信封是有由(w,h)这样的二维数对组成。

我们先按照宽度w进行升序排序，如果遇到w相同的情况，则按照高度h降序排序。最后把所有的h组成一个新的数组，进行最长递增子序列。就是最后的答案。

class Solution {
public:
    int maxEnvelopes(vector<vector<int> >& envelopes) {
        int n = envelopes.size();
        //按宽度升序排列，如果宽度一样，则按照高度降序排列
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& e1, const vector<int>& e2){
            if(e1[0] == e2[0]) return e1[1] > e2[1];
            return e1[0] < e2[0];
        });
        //对高度数组寻找 LIS
        vector<int> height(n);
        for(int i = 0; i < n; i++){
            height[i] = envelopes[i][1];
        }
        return lengthOfLIS(height);
    }
  	//最长递增子序列
    int lengthOfLIS(vector<int>& nums) {
        vector<int> top(nums.size(), 0);
        // 牌堆数初始化为0
        int piles = 0;
        for(int i = 0; i < nums.size(); i++){
            // 想要处理的扑克牌
            int poker = nums[i];

            // 搜索左侧边界的二分查找
            int left = 0, right = piles;
            while(left < right){
                int mid = (left + right) / 2;
                if(top[mid] > poker){
                    right = mid;
                }else if(top[mid] < poker){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }

            // 没找到合适的牌堆，新建一堆
            if(left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        return piles;
    }
};