俄罗斯套娃信封问题

2021-03-04

354. 俄罗斯套娃信封问题

难度困难427收藏分享切换为英文接收动态反馈

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

1
2
3

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

1 2	输入：envelopes = [[1,1],[1,1],[1,1]] 输出：1

提示：

1 <= envelopes.length <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 104

动态规划

第一维升序排列
第二维度降序排列

根据题目的要求，如果我们选择了 k 个信封，它们的的宽度依次为 $w_0, w_1, \cdots, w_{k-1}$，高度依次为 $h_0, h_1, \cdots, h_{k-1}$，那么需要满足：

$\begin{cases} w_0 < w_1 < \cdots < w_{k-1} \ h_0 < h_1 < \cdots < h_{k-1} \end{cases}$

同时控制 w 和 h 两个维度并不是那么容易，因此我们考虑固定一个维度，再在另一个维度上进行选择。例如，我们固定 w 维度，那么我们将数组 $\textit{envelopes}$中的所有信封按照 w 升序排序。这样一来，我们只要按照信封在数组中的出现顺序依次进行选取，就一定保证满足：

$w_0 \leq w_1 \leq \cdots \leq w_{k-1}$了。然而小于等于$ \leq$和小于 $< $还是有区别的，但我们不妨首先考虑一个简化版本的问题：

如果我们保证所有信封的w值互不相同，那么我们可以设计出一种得到答案的方法吗？

在 w 值互不相同的前提下，小于等于 $\leq$ 和小于 $<$ 是等价的，那么我们在排序后，就可以完全忽略 w 维度，只需要考虑 h 维度了。此时，我们需要解决的问题即为：

给定一个序列，我们需要找到一个最长的子序列，使得这个子序列中的元素严格单调递增，即上面要求的：

$h_0 < h_1 < \cdots < h_{k-1}$那么这个问题就是经典的「最长严格递增子序列」问题了，读者可以参考力扣平台的 300. 最长递增子序列及其官方题解。最长严格递增子序列的详细解决方法属于解决本题的前置知识点，不是本文分析的重点，因此这里不再赘述，会在方法一和方法二中简单提及。

当我们解决了简化版本的问题之后，我们来想一想使用上面的方法解决原问题，会产生什么错误。当 w 值相同时，如果我们不规定 h 值的排序顺序，那么可能会有如下的情况：

排完序的结果为 [(w, h)] = [(1, 1), (1, 2), (1, 3), (1, 4)]，由于这些信封的 w值都相同，不存在一个信封可以装下另一个信封，那么我们只能在其中选择 11 个信封。然而如果我们完全忽略 w 维度，剩下的 h 维度为[1, 2, 3, 4]这是一个严格递增的序列，那么我们就可以选择所有的4 个信封了，这就产生了错误。

因此，我们必须要保证对于每一种 w 值，我们最多只能选择 1 个信封。

我们可以将 h 值作为排序的第二关键字进行降序排序，这样一来，对于每一种 w 值，其对应的信封在排序后的数组中是按照 h 值递减的顺序出现的，那么这些 h 值不可能组成长度超过 1 的严格递增的序列，这就从根本上杜绝了错误的出现。

因此我们就可以得到解决本题需要的方法：

首先我们将所有的信封按照 w 值第一关键字升序、h 值第二关键字降序进行排序；

随后我们就可以忽略 w 维度，求出 h 维度的最长严格递增子序列，其长度即为答案。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes,new Comparator<int[]>(){
            @Override
            public int compare(int []o1,int []o2){
                return o1[0]-o2[0]==0?o2[1]-o1[1]: o1[0]-o2[0];
            }
        });

        int n=envelopes.length;
        int []dp=new int[n];
        
        Arrays.fill(dp, 1);
        int ans=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(envelopes[j][1]<envelopes[i][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}

基于二分查找的动态规划

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) {
            return 0;
        }
        
        int n = envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0]) {
                    return e1[0] - e2[0];
                } else {
                    return e2[1] - e1[1];
                }
            }
        });

        List<Integer> f = new ArrayList<Integer>();
        f.add(envelopes[0][1]);
        for (int i = 1; i < n; ++i) {
            int num = envelopes[i][1];
            if (num > f.get(f.size() - 1)) {
                f.add(num);
            } else {
                int index = binarySearch(f, num);
                f.set(index, num);
            }
        }
        return f.size();
    }

    public int binarySearch(List<Integer> f, int target) {
        int low = 0, high = f.size() - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (f.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/russian-doll-envelopes/solution/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/russian-doll-envelopes/solution/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最长严格递增子序列问题

方法：动态规划（这是使用动态规划解决的一个经典问题）

明确题目中的条件：

子序列：不要求连续子序列，只要保证元素前后顺序一致即可；
上升：这里的「上升」是「严格上升」，例如： [2, 3, 3, 6, 7] 这样的子序列是不符合要求的。

题目只问最长上升子序列的长度，没有问最长上升子序列是什么，因此考虑使用动态规划。

第 1 步：状态定义。dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。即：在 [0, ..., i] 的范围内，选择以数字 nums[i] 结尾可以获得的最长上升子序列的长度。

说明：以 nums[i] 结尾，是子序列动态规划问题的经典设计状态思路，思想是动态规划的无后效性（定义得越具体，状态转移方程越好推导）。

第 2 步：推导状态转移方程：遍历到 nums[i] 的时候，我们应该把下标区间 [0, ... ,i - 1] 的 dp 值都看一遍，如果当前的数 nums[i] 大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的数都看了， dp[i] 就是它们的最大值加 $1$。即比当前数要小的那些里头，找最大的，然后加 $1$ 。

状态转移方程即：dp[i] = max(1 + dp[j] if j < i and nums[j] < nums[i])。

第 3 步：初始化。单独一个数是子序列，初始化的值为 1；

第 4 步：输出。应该扫描这个 dp 数组，其中最大值的就是题目要求的最长上升子序列的长度。

Java 代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return len;
        }
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            // 看以前的，比它小的，说明可以接在后面形成一个更长的子序列
            // int curMax = Integer.MIN_VALUE; 不能这样写，万一前面没有比自己小的，
            // 这个值就得不到更新
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            
            // 在遍历的时候同时找 dp 数组的最大值
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

时间复杂度：O(N^2)，这里 N 是输入数组的长度；空间复杂度：O(N)。

补充说明：这道题还有一个经典的，时间复杂度为 O(N \log N) 的解法，它也是动态规划的解法，可以在题解区找到这个方法的解释和代码。

liweiwei1419的评论