354. Russian Doll Envelopes

Question

You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Solution 1

最长递增子数列

这道题是LIS问题（Longest Increasing Subsequence） 的升级版。
后一个数组中的两个元素应该同时严格大于前一个数组中的两个元素。
因此我们需要维护一个宽度和高度同时严格单调递增的数列。

排序

我们可以对数组以宽度进行比较排序。当二者的宽度相等时，以高度的倒序排序。
（采用倒序排序是为了下面处理时排除不严格大于上一个数组的情况。）

递增数列

我们可以维护一个递增动态数组arr，记录高度组成的单调递增数列。（LIS）
首先将数组中的第一个元素的高度加入动态数组。
然后遍历数组envelopes[]：

• 如果当前数组的高度height大于单调递增数列的最大值：
  • 则当前的数组的宽度和高度均严格大于数组中最后一个高度对应的数组。
  • 数组是优先以宽度的顺序排列，相等时以高度的倒序排列。由于相同宽度时高度大的在前，因此当当前高度大于之前的最大高度，则宽度也一定大于之前的最大宽度。
• 如果小于或者等于单调递增数列的最大值：
  • 单调数列中高度的增长越平缓，我们在后面找到更多严格大于height的可能性就越大，因此可以用贪心思想，更新单调数列中的第一个大于当前高度的值。
  • 由于单调递增数列是有序的，因此可以采用二分搜索来寻找第一个大于当前高度的值的下标，并将其更新为当前的height。

排序的时间复杂度为O(nlogn)，遍历数组的时间复杂度为O(n)，二分搜索的时间复杂度为O(logn)。
总的时间复杂度为O(nlogn)。

Code

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        List<Integer> arr = new ArrayList<>();
        arr.add(envelopes[0][1]);
        for(int i = 1; i < envelopes.length; i++){
            int height = envelopes[i][1];
            if(height > arr.get(arr.size()-1)){
                arr.add(height);
            }
            else{
                int index = Collections.binarySearch(arr, height);
                if(index < 0) index = -index-1;
                arr.set(index, height);
            }
        }
        return arr.size();
    }
}

Solution 2

注意这个方法在LeetCode中会超时，仅仅是记录一下思路，也可以采用动态规划的方法。
记忆化搜索剪枝。
记忆化搜索每个envelope。

memorazation()方法，返回当前的envelope中可以包含的最大数量。
当数组memo[i]不等于0时，返回memo[i]。
否则初始化最大值max为1。
遍历数组中的所有元素，如果宽度于长度都大于envelopes[i]，则向下递归搜索该元素。
比较并更新max和递归结果的返回值+1。
最后将当前位置memo[i]设置为包含的最大数量max。

遍历所有元素时间复杂度O(n)。
记忆化搜索元素的子项时间复杂度O(n)。
时间复杂度为O(n2)。

Code

class Solution {
    int[][] dolls;
    int[] memo;
    
    public int maxEnvelopes(int[][] envelopes) {
        dolls = envelopes;
        memo = new int[dolls.length];
        int res = 0;
        for(int i = 0; i < dolls.length; i++){
            if(memo[i] != 0) continue;
            memorazation(i);
            res = Math.max(res, memo[i]);
        }
        return res;
    }
    
    private int memorazation(int i){
        if(memo[i] != 0){
            return memo[i];
        }
        int max = 1;
        for(int k = 0; k < dolls.length; k++){
            if(dolls[k][0] < dolls[i][0] && dolls[k][1] < dolls[i][1]){
                max = Math.max(max, memorazation(k) + 1);
            }
        }
        return memo[i] = max;
    }
}