1.题目

给你一个二维整数数组 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

提示：
1 <= envelopes.length <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 104

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

2.思路

（1）思路1
在做此题之前，需要先了解300.最长递增子序列这题，该题是在⼀维数组里面求元素的最长递增子序列，而本题则可以看作其升级版，是在二维平面里面求最长递增子序列。题中信封是由 [w, h] 这样的数对形式表示的，具体思路如下：
① 先对宽度 w 进行升序排序，如果w 相同，则按照高度 h 降序排序。
② 之后再把所有的 h 作为⼀个数组，那么这个数组上的最长递增子序列的长度就是答案。

3.代码实现（Java）

//思路1
public int maxEnvelopes(int[][] envelopes) {
    //n为总的信封数量
    int n=envelopes.length;
    //对宽度w进行升序排序，如果w相同，则按照高度h降序排序
    Arrays.sort(envelopes,new Comparator<int[]>(){
        //重写compare方法，即自定义排序规则
        public int compare(int[] a,int[] b){
            return a[0]==b[0] ? (b[1]-a[1]) : (a[0]-b[0]);
        }
    });
    //所有的 h 组成⼀个数组heights，那么这个数组上的最长递增子序列的长度就是答案
    int[] heights=new int[n];
    //初始化heights
    for(int i=0;i<n;i++){
        heights[i]=envelopes[i][1];
    }
    return lengthOfLIS1(heights);
    //return lengthOfLIS2(heights);
}

//使用动态规划求解LIS
public int lengthOfLIS1(int[] nums) {
    int length = nums.length;
    //dp[i]:表示数组nums中以nums[i]结尾的最长递增子序列的长度
    int[] dp=new int[length];
    //将dp数组中的所有元素全部初始化为1
    Arrays.fill(dp,1);
    for(int i=0;i<length;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
    }
    //dp数组中的最大值即为所数组nums中最长递增子序列的长度
    int res=0;
    for(int i=0;i<length;i++){
        res=Math.max(res,dp[i]);
    }
    return res;
}

//二分搜索
public int lengthOfLIS2(int[] nums) {
    int length = nums.length;
    //定义堆顶元素数组，top[i]表示第i个堆的堆顶元素
    int[] top=new int[length];
    //堆数初始化为0
    int piles=0;
    for(int i=0;i<length;i++){
        //当前要处理的元素
        int ele=nums[i];
        //搜索左侧边界的二分搜索
        int left=0,right=piles;
        while(left<right){
            int mid=left+(right-left)/2;
            if(top[mid]<ele){
                left=mid+1;
            }else if(top[mid]>ele){
                right=mid;
            }else if(top[mid]==ele){
                //收缩右侧边界
                right=mid;
            }
        }
        //没有找到合适的堆，新建一个堆
        if(left==piles){
            piles++;
        }
        //将该元素放到堆顶
        top[left]=ele;
    }
    //最后得到的堆数即为最长递增子序列的长度
    return piles;
}