2018-08-24 LeetCode354. 俄罗斯套娃信封问

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0)return 0;
        Arrays.sort(envelopes,new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {    
                if(o1[0] == o2[0])return o2[1] - o1[1];
                return o1[0] - o2[0];
            }
        });
        int max;
        int res = 0;
        for (int i = 1; i < envelopes.length; i++) {
            max = 0;
            for (int j = res; j >= 0; j--) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    max = j + 1;
                    res = Math.max(res, max);
                    break;
                }
            }
            if( max==res || envelopes[i][1]<envelopes[max][1])
                envelopes[max][1]=envelopes[i][1];
        }
        return res+1;
    }
}

先按a从小到大进行排序，当a相同时，按b从大到小排序。然后求解b的最长递增子序列。
当前数arr[i]大于ends数组中所有的数(末尾的最大)，我们会将arr[i]添加在ends数组中；否则在ends数组中二分查找第一个大于当前数的数且替换它。所以我们的做法会保证在a相等的情况下，b可以有一个最小值，这样可以摞相对多的数。以达更长的序列，同时也避免了a相同b不相同时摞在一起的情况。

private static class Node{
        public int a;
        public int b;
        public Node(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    public static class MyComparator implements Comparator<Node>{
        @Override
        public int compare(Node o1, Node o2) {
            if(o1.a == o2.a){
                return o2.b - o1.b;
            }else {
                return o1.a - o2.a;
            }
        }
    }

    /**
     * 最长递增子序列的OLogN方法
     * @param envelopes
     * @return
     */
    public static int maxEnvelopes(int[][] envelopes) {
        if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0)return 0;
        Node[] nodes = new Node[envelopes.length];
        for(int i = 0; i < envelopes.length; i++){
            nodes[i] = new Node(envelopes[i][0],envelopes[i][1]);
        }
        Arrays.sort(nodes,0,nodes.length,new MyComparator());
        int[] ends = new int[envelopes.length];
        ends[0] = nodes[0].b;
        int right = 0;
        int l = 0,m = 0,r = 0;
        int res = 1;
        for(int i = 1; i < nodes.length; i++){
            l = 0;
            r = right;
            while(l <= r){
                m = l + (r-l)/2;
                if(nodes[i].b > ends[m]){
                    l = m + 1;
                }else {
                    r = m - 1;
                }
            }
            right = Math.max(l,right);
            ends[l] = nodes[i].b;
        }
        return right + 1;
    }