LeetCode354：俄罗斯套娃信封问题

题意

求二维最长上升子序列

Solution

对第一维进行从小到大排序，然后第二维从大到小排序，对第二维做LIS即可。

Code

class Solution {
    public int maxEnvelopes(int[][] a) {
        int n = a.length;
        if (n == 0)
            return 0;

        int[] low = new int[n + 1];
        int res = 0;
        Arrays.sort(a, new Comparator<int[]> () {
            public int compare(int[] c1, int[] c2) {
                if (c1[0] == c2[0]) {
                    return c2[1] - c1[1];
                } else {
                    return c1[0] - c2[0];
                }
            }
        });
        for (int i = 0; i < n; i++)
        {
            if (low[res] < a[i][1])
                low[++res] = a[i][1];
            else{
                int pos = Arrays.binarySearch(low, 1, res, a[i][1]);
                if (pos < 0)
                    pos = -pos - 1;
                low[pos] = a[i][1];
            }
        }
        return res;
    }
}