354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

一刷
题解：
首先对数组根据width进行排序, 如果width相同, height递减
然后就变成了寻找longest increasing subsequence的子问题。注意，这个dp数组存储递增序列。
Time complexity O(nlogn), space complexity O(n)

public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes == null || envelopes.length == 0) return 0;
        //Ascend on width and descend on height if width are same.
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return b[1] - a[1];
                else return a[0] - b[0];//first compare width
            }
        });
        int[] dp = new int[envelopes.length];
        int len = 0;
        for(int[] envelope : envelopes){
            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
            if(index<0) index = -(index+1);//the insert point
            dp[index] = envelope[1];//height
            if(index == len) len++;
        }
        
        return len;
    }
}

二刷：
注意，为了不把[4,5], [4,6]算做一组有效的值，当长相等时，宽用逆序。保证只有一个被算进去。
排序后变为[4,6],[4,5].
分析：怎样用binarySearch找到需要insert的地方。用最典型的binarysearch的写法就能实现。因为，最后一个点的时候，i,j肯定相邻，mid处于i的地方，如果大于i，则Insert的地方为j， 否则为i. 即满足lo == hi的点。但是注意dp的数组需要先fill Integer.MAX_VALUE

public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int len = envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return b[1] - a[1];
                else return a[0] - b[0];
            }
        });
        
        int[] dp = new int[len];
        Arrays.fill(dp, Integer.MAX_VALUE);
        len = 0;
        for(int[] env : envelopes){
          int index = bs(dp, 0, len, env[1]);
            dp[index] = env[1];
            if(index == len) len++;
        }
        return len;
    }
    
    public int bs(int[] dp, int lo, int hi, int target){
        while(lo<=hi){
            int mid = lo + (hi-lo)/2;
            if(dp[mid] == target) return mid;
            else if(dp[mid]<target) lo = mid+1;
            else hi = mid-1;
        }
        return lo;
    }
}

三刷
题解：有两个需要特别注意的地方
一个是sort的时候，如果根据width排序，如果width相等，height高的在前。
一个是dp数组初始化的时候要Arrays.fill(dp, Integer.MAX_VALUE), 这样才能用binarySearch找到正确的位置。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return b[1] - a[1];
                else return a[0] - b[0];
            }
        });
        
        //longest ascending subsequence
        int len = 0;
        int[] res = new int[envelopes.length];
        Arrays.fill(res,  Integer.MAX_VALUE);
        for(int i=0; i<envelopes.length; i++){
            int height = envelopes[i][1];
            int index = Arrays.binarySearch(res, height);
            if(index<0) index = -(index+1);
            if(index == len) len++;
            res[index] = height;
        }
        return len;
    }
}