题目

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

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

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

注意：不允许旋转信封。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/russian-doll-envelopes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。`

解题思路

排序:长度由小到大,长度一样的时候高度由大到小

得到一个数组:5326462
结论，这个数组中最长递增子序列长度就是套娃最多能套多少层
长度跟我一样的东西,高度不如我的,在我后面
那么只要左侧高度小于我，它长度必须小于我，我所形成的递增子序列必能套进去
我们排除了干扰项，为什么高度要由大到小排，就是为了防止高度比我小的，在我左边干扰我形成递增子序列

代码

class Solution {
    public class Envelope{
        public int l;
        public int h;
        public Envelope(int width,int height){
            this.l=width;
            this.h=height;
        }
    }
    public class envelopeComparator implements Comparator<Envelope>{
        public int compare(Envelope o1,Envelope o2){
            return o1.l!=o2.l?o1.l-o2.l:o2.h-o1.h;
        }
    }
    public int maxEnvelopes(int[][] envelopes) {
        int n=envelopes.length;
        Envelope[] env=new Envelope[n];
        for(int i=0;i<n;i++){
            env[i]=new Envelope(envelopes[i][0],envelopes[i][1]);
        }
        Arrays.sort(env,new envelopeComparator());
        int[] end=new int[n];
        end[0]=env[0].h;
        int right=0;
        int l=0;
        int r=0;
        int m=0;
        for(int i=1;i<n;i++){
            l=0;
            r=right;
            while(l<=r){
                m=l+(r-l)/2;
                if(env[i].h>end[m]){
                    l=m+1;
                }else{
                    r=m-1;
                }
            }
            right=Math.max(right,l);
            end[l]=env[i].h;
        }
        return right+1;
    }

}

        

          
        
        
        

          

          AI 代码解读