354. Russian Doll Envelopes

Version #2
牛逼。。。 和dp一样先sort
然后对Height找longest increasing subsequence
看下面的神讲解

Time O(nlogn)
Space O(n)

1. Sort the array. Ascend on width and descend on height if width are same.
2. Find the longest increasing subsequence based on height.

---

• Since the width is increasing, we only need to consider height.
• [3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4]
• 
  

二刷
55.74 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // a[0]->w, a[1]->h
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        int len = envelopes.length;
        // dp[i] -> the lowest height to form a Russian Doll with size i - 1
        int[] dp = new int[len + 1];
        // find the first height larger than curr, if not found, curr is i + 1
        int count = 0;
        for (int[] envelope : envelopes) {
            int curr = envelope[1];
            int start = 1;
            int end = count;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (dp[mid] < curr) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            if (dp[start] >= curr) {
                dp[start] = curr;
            } else {
                count++;
                dp[count] = curr;
            }
        }
        return count;
    }
}

一刷
55.17 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        // Sort with width, if width equals, sort with height
        Arrays.sort(envelopes, (e1, e2) -> {
            if (e1[0] == e2[0]) {
                return e2[1] - e1[1]; // height
            } else {
                return e1[0] - e2[0];
            }
        });
        // Find longest increasing sequence for height
        int[] minEnd = new int[envelopes.length];
        int max = 0;
        minEnd[0] = envelopes[0][1];
        for (int i = 1; i < envelopes.length; i++) {
            // Given envelopes[i] with its height envelopes[i][1] find the first element that is larger or equal to current height, replace is
            // If not found, increate max
            int start = 0;
            int end = max;
            int currHeight = envelopes[i][1];
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (minEnd[mid] < currHeight) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            if (minEnd[start] >= currHeight) {
                minEnd[start] = currHeight;
            } else {
                max++;
                minEnd[max] = currHeight;
            }
        }
        return max + 1;
    }
}



Version #1 Straight Forward DP

O(nlogn) for sorting and O(n^2) for dp, so Time O(n^2)
Space O(n)

二刷
32.44 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // a[0]->w, a[1]->h
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        int result = 0;
        int len = envelopes.length;
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = 1 + max;
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}


一刷
3.93 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        // Sort with width, if width equals, sort with height
        Arrays.sort(envelopes, (e1, e2) -> {
            if (e1[0] == e2[0]) {
                return e1[1] - e2[1];
            } else {
                return e1[0] - e2[0];
            }
        });
        int result = 0;
        int len = envelopes.length;
        // dp[i] -> max number of envelopes that current envelop can contain
        int[] dp = new int[len];
        dp[0] = 1;
        for (int curr = 0; curr < len; curr++) {
            int max = 0;
            for (int prev = 0; prev < curr; prev++) {
                if (envelopes[curr][0] > envelopes[prev][0] && envelopes[curr][1] > envelopes[prev][1]) {
                    max = Math.max(dp[prev], max);
                }
            }
            dp[curr] = max + 1;
            result = Math.max(result, dp[curr]);
        }
        return result;
    }
}