LeetCode 354. 俄罗斯套娃信封问题

1、题目

2、分析

这个问题也是最长子序列的问题。
具体分析可以参考：
https://labuladong.github.io/zgnb/3/15/17/

这里需要注意自定义数组排序的应用，还有二分查找法的使用

3、代码

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        //排序
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            }
        });
        int[] heigth = new int[envelopes.length];
        for(int i = 0; i < envelopes.length; i ++){
            heigth[i] = envelopes[i][1];
        }
        //计算最长子序列
        return lengthOfLIS(heigth);
    }

    private int lengthOfLIS(int[] nums){
        int piles = 0;
        int[] top = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            int poker = nums[i];
            int left = 0;
            int rigth = piles;
            while(left < rigth){
                int mid = (left + rigth) / 2;
                if(top[mid] >= poker)
                    rigth = mid;
                else
                    left = mid + 1;
            }
            if(left == piles) piles++;
            top[left] = poker;
        }
        return piles;
    }
}