数据结构和算法【30】俄罗斯套娃信封问题

https://leetcode.cn/problems/russian-doll-envelopes/

public class CodingDemo {

    /**
     * TODO: 俄罗斯套娃信封问题
     * @param envelopes
     * @return
     */
    private static int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0 || envelopes[0] == null || envelopes[0].length == 0){
            return 0;
        }

        //1，把原始数组转换为排序信封数组
        Envelop[] arr = getEnvelops(envelopes);

        //2, 创建辅助数组ends[]
        // ends[b]=c，表示长度为 b+1 的最长递增子序列，最小的结尾值是c
        // 初始的时候 ends[0] = arr[0].wide, 即长度为1的序列，就是 arr[0].wide
        int[] ends = new int[arr.length];
        ends[0] = arr[0].wide;

        //右边界
        int right = 0;

        for (int i = 1; i < arr.length; i++) {

            //在 ends[l ~ r] 范围内查找是否有值大于arr[i].wide
            //如果有，则更新对应的值为 arr[i].wide，
            //因为 ends[b]=e 中 e 是长度为b+1的最长递增子序列的最小结尾

            // 如果 ends[l ~ r] 值，没有大于 arr[i].wide的，则说明最长递增子序列的值需要增加了，也就是right边界右移
            //否则，替换 arr[i]
            int l = 0;
            int r = right;

            //二分查找
            while (l <= r){
                int mid = (l+r)/2;
                if (arr[i].wide > ends[mid]){
                    l = mid+1;
                } else {
                    r = mid-1;
                }
            }

            //判断right边界
            right = Math.max(right, l);
            //更新递增子序列最小结尾
            ends[l] = arr[i].wide;
        }
        //最长递增子序列就是 right+1
        return right+1;
    }

    /**
     * 把给定数组转换为有序信封数组
     * @param envelopes
     * @return
     */
    private static Envelop[] getEnvelops(int[][] envelopes){
        Envelop[] res = new Envelop[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) {
            res[i] = new Envelop(envelopes[i][0], envelopes[i][1]);
        }
        //使用自定义比较器对生成的信封数组排序
        Arrays.sort(res, new EnvelopComparator());
        return res;
    }

    //自定义信封类，包括信封长度和宽度
    private static class Envelop{
        int len;
        int wide;

        public Envelop(int len, int wide) {
            this.len = len;
            this.wide = wide;
        }
    }

    //自定义信封类比较器
    private static class EnvelopComparator implements Comparator<Envelop> {

        @Override
        public int compare(Envelop o1, Envelop o2) {
            //长度相等时，宽度大的在前
            //否则按照长度由小到大排列
            return o1.len == o2.len ? o2.wide - o1.wide : o1.len - o2.len;
        }
    }

    public static void main(String[] args) {
        int[][] arr = {
                {5,4},
                {6,4},
                {6,7},
                {2,3}
        };
        System.out.println(maxEnvelopes(arr));
    }
}

D:\java\bin\java.exe
3