Leetcode 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]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/russian-doll-envelopes

这道题的解法是⽐较巧妙的：

先对宽度 w 进⾏升序排序，如果遇到 w 相同的情况，则按照⾼度 h 降序排序。之后把所有的 h 作为⼀个数组，在这个数组上计算 LIS 的⻓度就是答案。

画个图理解⼀下，先对这些数对进⾏排序：

然后在 h 上寻找最⻓递增⼦序列： 

这个⼦序列就是最优的嵌套⽅案。

这个解法的关键在于，对于宽度 w 相同的数对，要对其⾼度 h 进⾏降序排序。因为两个宽度相同的信封不能相互包含的，逆序排序保证在 w 相同的数对中最多只选取⼀个。 

class Solution {
    //动态规划
    
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        //对二维数组进行降维：先对信封宽度w进行升序排序，简化为一维，然后对高度求最长上升子序列
        Arrays.sort(envelopes, new Comparator(){
            public int compare(int[] a, int[] b){
                //如果宽度相同，则按照高度降序排列，保证最多只有一个信封能用
                if(a[0] == b[0]){
                    return b[1] - a[1];
                }
                return a[0] - b[0];
            }
        });

        //对高度数组进行LIS
        int[] height = new int[n];
        for(int i = 0; i < n; i++){
            height[i] = envelopes[i][1];
        }
        
        return lengthOfLIS(height);
    }

    //辅助方法：二分搜索，类似于蜘蛛纸牌游戏，最后牌堆的堆数就是最长上升子序列的长度
    public int lengthOfLIS(int[] nums) {
        //top数组：表示牌堆
        int[] top = new int[nums.length];
        //牌堆数初始化为0
        int piles = 0;
        //依次处理每张牌
        for(int poker : nums){
            //
            int left = 0, right = piles;
            while(left < right){
                int mid = left + (right - left) / 2;
                if(top[mid] == poker){
                    right = mid;
                }else if(top[mid] > poker){
                    right = mid;
                }else if(top[mid] < poker){
                    left = mid + 1;
                }
            }
            ///
            //如果没找到合适的牌堆，就新建一堆
            if(left == piles){
                piles++;
            }
            //把这张牌放到对应的牌堆顶
            top[left] = poker;
        }
        //牌堆数就是最长上升子序列的长度
        return piles;
    }
}

时间复杂度为 O(NlogN) ，因为排序和计算 LIS 各需要 O(NlogN)的时间。空间复杂度为 O(N) ，因为计算 LIS 的函数中需要⼀个 top 数组。