LeetCode[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]).

DP

复杂度

O(N^2),O(N)

思路

先排序，然后建立dp数组。dp[i]表示，到第i位能组成的最大的信封的个数。

代码

public int maxEnvelopes(int[][] envelopes) {    if(envelopes == null || envelopes.length == 0) return 0;    // sort the envelopes;    Arrays.sort(envelopes, new Comparator
    
     (){        public int compare(int[] a1, int[] a2) {            return a1[0] - a2[0];        }    });    // use dp;    int res = 0;    int[] dp = new int[envelopes.length];    for(int i = 0; i < envelopes.length; i ++) {        for(int j = 0; j < i; j ++) {            if(envelopes[j][1] < envelopes[i][1] && envelopes[j][0] < envelopes[j][0]) {                dp[i] = Math.max(dp[i], dp[j] + 1);                res = Math.max(res, dp[i]);            }        }    }    return res;}
    

Binary Search

复杂度

O(NlgN),O(N)

思路

先将数组按照升序排序，然后将height按照。在无序的数组中找最长的increasing序列的方式处理。tricky的部分，在于，对于相同width的信封，要将高度按降序排列。如果按升序排列的话，考虑corner case：2,36,4

代码

public int maxEnvelopes(int[][] envelopes) {    if(envelopes == null || envelopes.length == 0) return 0;    // sort the envelopes first;    Arrays.sort(envelopes, new Comparator
    
     (){        public int compare(int[] a, int []b) {            if(a[0] == b[0]) {                return b[1] - a[1];            }            return a[0] - b[0];        }    });    // using nlgn;    int len = 0;    int[] dp = new int[envelopes.length];    for(int[] arr : envelopes) {        int index = doBinary(dp, 0, len - 1, arr[1]);        dp[index] = arr[i];        if(index == len) len ++;    }    return len;}// using binary search, to find where to insert the val;public int doBinary(int[] dp, int left, int right, int val) {    while(left < right) {        int mid = getMid(left, right);        if(dp[mid] >= val) {            right = mid - 1;        }        else {            left = mid + 1;        }    }    return left;}public int getMid(int left, int right) {    return left + (right - left) / 2;}