354. 俄罗斯套娃信封问题（禁止套娃！）

2021-03-05 本文已影响0人闭门造折

力扣题解《禁止套娃！（图解过程）》

方法一：比较暴力的动态规划

思路

状态定义:
- $dp[i]$ 表示仅使用信封 $[0, i]$ (这里是区间的意思，表示前 $i+1$ 个信封)，且以第 $i$ 个信封为顶端信封时的最大高度。
状态转移:
- 首先对整个数组根据宽度排序，宽的信封放在前面。
- 设 $j∈[0, i)$ ,考虑每轮计算新的 $dp[i]$ 时，遍历 $[0, i)$ 区间，做以下判断：
1. 当 $envelopes[j][0] > envelopes[i][0]$ 且 $envelopes[j][1] > envelopes[i][1]$ 时：认为信封 $j$ 严格大于信封 $i$ ，此时尝试更新底座最大高度 $maxh$ : maxh = max(maxh, dp[j])
2. 当信封 $j$ 不严格大于信封 $i$ 时：跳过。
- 全部遍历完成后，更新 $dp[i]$ ：dp[i] = maxh + 1。理解为在最大可放置的高度上，再放上当前信封。
- 转移方程： dp[i] = max(dp[j]) + 1 (j ∈ [0, i) 且信封j比信封i严格大)
初始状态:
- $dp[i]$ 所有元素置0，当计算后才进行赋值。
返回值:
- 返回 $dp$ 列表最大值，即可得最大套娃层数。

复杂度分析

时间复杂度 $O(N^2)$ ：排序需要 $O(NlogN)$ ，遍历 $dp$ 列表需要 $O(N)$ ，计算每一个 $dp[i]$ 需要 $O(N)$
空间复杂度 $O(N)$ ：dp列表占用 $O(N)$ 空间

快乐小视频

具体代码：

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        // 先按照宽做排序，越大的放在越前面
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
            return a[0] > b[0];
        });

        // 预开空间(不妨多开几个防溢出)
        vector<int> dp(n + 5);

        int ans = 0;
        // 依次尝试放置每个信封
        for(int i = 0; i < n; i++){
            // 遍历他之前的每个信封，看能放下他且最多层的个数
            int maxh = 0;
            for(int j = 0; j < i; j++){
                // 判断是否可以放下当前的信封
                if(envelopes[j][0] > envelopes[i][0]
                && envelopes[j][1] > envelopes[i][1]){
                    // 如果可以放下当前信封，看看是不是最大高度
                    if(maxh < dp[j]){
                        maxh = dp[j];
                    }
                }
            }
            // 遍历一圈，找到最高，且能放下当前信封的maxh
            dp[i] = maxh + 1;

            // 判断当前信封高度是不是最高高度
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

用C++提交花费了1264 ms，确实挺慢的，看其他题解里写不同语言可能会超时。

但是确实这个思路最好想，也可以很方便的套用到面试题 08.13. 堆箱子这道题上。

方法二：第二维参与排序

思路

目标是将二维问题，转换为我们所熟悉的一维的最长上升子序列问题。因此需要降维，想办法在计算时，仅考虑 $h$ 的顺序即可，忽略 $w$ 影响。

状态定义:
- $dp[i]$ 表示仅使用信封 $[0, i]$ ，且以第 $i$ 个信封为底部信封时的最大高度。
状态转移:
- 首先对整个数组按照宽度由小到大排序，排序同时，对于宽度相同的项，根据高度由大到小排序。
假如我们仍像方法一一样，仅针对宽度排序。那么对于形如 $[4, 4]$ 和 $[4, 5]$ 的两项，由于 $[4, 4]$ 排序在 $[4, 5]$ 之前，这就导致仅考虑h时，我们认为 $[4, 4]$ 和 $[4, 5]$ 可以构成一组“套娃”。但是按照“二维严格升序”的定义，两个矩形的宽相等，不属于严格升序。

为了规避上述的问题，我们对宽度相等的两个矩形，使用高度降序排序，这样一来，上述问题的排列将变成： $[4, 5], [4, 4]$ 。在我们计算最长上升子序列时，由于 $5>4$ ，也就不会出现“错误套娃”。
- 排序完毕后，提取出所有的h，形成一个新的数组。对新的数组执行“最长上升子序列”问题的求解:
- 设 $j∈[0, i)$ ,考虑每轮计算新的 $dp[i]$ 时，遍历 $[0, i)$ 区间，做以下判断：
1. 当 $envelopes[j][1] > envelopes[i][1]$ 时：认为信封 $j$ 严格大于信封 $i$ ，此时尝试更新 $dp[i]$ : dp[i] = max(dp[i], dp[j] + 1)
2. 当信封 $j$ 不严格大于信封 $i$ 时：跳过。
- 转移方程： dp[i] = max(dp[j]) + 1 (j ∈ [0, i) 且信封j比信封i高度严格大)
初始状态:
- $dp[i]$ 所有元素置1，表示该信封可独自形成层数为1的套娃。
返回值:
- 返回 $dp$ 列表最大值，即可得最大套娃层数。

复杂度分析

时间复杂度 $O(N^2)$ ：排序需要 $O(NlogN)$ ，遍历 $dp$ 列表需要 $O(N)$ ，计算每一个 $dp[i]$ 需要 $O(N)$
空间复杂度 $O(N)$ ：dp列表占用 $O(N)$ 空间

快乐小视频

具体代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();

        // 首先执行排序，按照宽度排序，小的在前大的在后
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
            if(a[0] == b[0]){
                // 对于宽度相等的信封，根据高度逆序，大的在前小的在后
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });

        // 预开空间,设初始值为1,即仅包含当前信封
        vector<int> dp(n, 1);

        int ans = 0;
        // 计算最长上升子序列
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(envelopes[j][1] < envelopes[i][1]){
                    // 如果h严格升序，尝试更新dp[i]
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            // 尝试更新最大值ans
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

比起方法一，有一定优化，但是优化效果仍然有限，使用C++提交的运行时间是1004 ms。

仍然是一个 $O(N^2)$ 的解决方法

方法三：维护单增序列

思路

更换想法，对方法二中最长上升子序列问题的求解做优化，不再维护长度为 $O(N)$ 的 $dp$ 数组，改为维护一条最长递增序列。

状态定义:
- $dp[i]$ 表示长度为 $i + 1$ 的最长上升子序列，第 $i$ 位的最小值。
状态转移:
- 同方法二，首先对整个数组按照宽度由小到大排序，排序同时，对于宽度相同的项，根据高度由大到小排序。
- 排序完毕后，提取出所有的h，形成一个新的数组。对新的数组执行“最长上升子序列”问题的求解:
  - 遍历 $[0, n)$ 区间，对每一个值 $x$ ，判断 $x$ 在单增序列 $dp$ 中的位置，做以下判断：
    1. 当 $dp$ 中仅存在某值满足 $y > x$ ：使用 $x$ 替换该值 $y$
    2. 当 $dp$ 中存在多值满足 $y_t > y_2 > y_1 > x$ ：使用 $x$ 替换符合条件的最小值 $y_1$
    3. 当 $dp$ 中不存在值满足 $y > x$ ：将 $x$ 添加到 $dp$ 数组最末端
    为什么可以这样做？：假设当前 $dp$ 队列为1, 3, 6。
    这翻译过来是：
    1. 存在一条上升子序列，长度为1，且以1为结尾；
    2. 存在一条上升子序列，长度为2，且以3为结尾；
    3. 存在一条上升子序列，长度为3，且以6为结尾。
    假设此时来了个新的值4，显然的，可以在长度为2且末尾为3的那条上升子序列后，再添加一个4，形成一条长度为3，且以4为结尾的上升子序列。
    同时更新 $dp$ 队列变成1,3,4。这是因为同样是长度为3，以6为结尾后，想继续扩充，新增的数字至少为7；而以4为结尾时，新增数字仅需至少为5即可。
    额外需要注意的是： $dp$ 的结果，不一定就是一条存在的上升子序列：仍然以1,3,6为例，假设此时新增的数字为2，则 $dp$ 更新为1,2,6。但实际上并不存在一条子序列，满足1,2,6。1,2,6仅可翻译为：
    1. 存在一条上升子序列，长度为1，且以1为结尾；
    2. 存在一条上升子序列，长度为2，且以2为结尾；
    3. 存在一条上升子序列，长度为3，且以6为结尾。
      - 转移方程： dp[index] = x (index为第一个大于x的值所在位置)
初始状态:
- $dp$ 仅有一个元素，为排序后第一个信封的 $h$ 值。
返回值:
- 返回 $dp$ 列表长度，即可得最大套娃层数。

复杂度分析

时间复杂度 $O(N^2)$ ：排序需要 $O(NlogN)$ ，遍历信封列表需要 $O(N)$ ，计算每一个信封插入位置需要 $O(N)$
空间复杂度 $O(N)$ ：dp列表占用 $O(N)$ 空间

快乐小视频

具体代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();

        // 首先执行排序，按照宽度排序，小的在前大的在后
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
            if(a[0] == b[0]){
                // 对于宽度相等的信封，根据高度逆序，大的在前小的在后
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });

        // 预开空间,初始值为排序后第一个信封的高度
        vector<int> dp(1, envelopes[0][1]);

        int ans = 0;
        // 计算最长上升子序列
        // 第0个元素已默认放入dp，因此从1开始遍历
        for(int i = 1; i < n; i++){
            // 搜索合适的更新位置
            int j = 0;
            for(; j < dp.size(); j++){
                // 需要注意，只要不小于当前大小，即可更新
                if(dp[j] >= envelopes[i][1]){
                    dp[j] = envelopes[i][1];
                    break;
                }
            }
            // 如果整个dp列表中，不含有比当前h大的值，则扩展dp列表
            if(j == dp.size()){
                dp.emplace_back(envelopes[i][1]);
            }
        }
        return dp.size();
    }
};

比起方法二，这个方法其实优化了很多，远不是 $O(N^2)$ 的复杂度，而是 $O(N * len(dp))$ 但是假如一开始给定的就是一个层层套娃的合法序列，那么最差时间复杂度仍然能达到 $O(N^2)$

方法四：二分查找

思路

方法三中，搜索插入位置的过程，用的是 $O(N)$ 的搜索插入，可以通过二分法，优化到 $O(logN)$ 。

状态定义:
- $dp[i]$ 表示长度为 $i + 1$ 的最长上升子序列，第 $i$ 位的最小值。
状态转移:
- 同方法二，首先对整个数组按照宽度由小到大排序，排序同时，对于宽度相同的项，根据高度由大到小排序。
- 排序完毕后，提取出所有的h，形成一个新的数组。对新的数组执行“最长上升子序列”问题的求解:
  - 遍历区间，对每一个值，判断在单增序列中的位置，做以下判断：
    1. **当 $dp$ 中仅存在某值 $y > x$ **：使用 $x$ 替换该值 $y$
    2. **当 $dp$ 中存在多值 $y_t > y_2 > y_1 > x$ **：使用 $x$ 替换符合条件的最小值 $y_1$
    3. 当 $dp$ 中不存在值满足 $y > x$ ：将 $x$ 添加到 $dp$ 数组最末端
  - 转移方程： dp[index] = x (index为第一个大于x的值所在位置)
初始状态:
- $dp$ 仅有一个元素，为排序后第一个信封的 $h$ 值。
返回值:
- 返回 $dp$ 列表长度，即可得最大套娃层数。

复杂度分析

时间复杂度 $O(NlogN)$ ：排序需要 $O(NlogN)$ ，遍历信封列表需要 $O(N)$ ，计算每一个信封插入位置需要 $O(logN)$
空间复杂度 $O(N)$ ：dp列表占用 $O(N)$ 空间

快乐小视频

没啥快乐小视频了，看看方法三的得了。

具体代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();

        // 首先执行排序，按照宽度排序，小的在前大的在后
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>& b){
            if(a[0] == b[0]){
                // 对于宽度相等的信封，根据高度逆序，大的在前小的在后
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });

        // 预开空间,初始值为排序后第一个信封的高度
        vector<int> dp(1, envelopes[0][1]);

        int ans = 0;
        // 计算最长上升子序列
        // 第0个元素已默认放入dp，因此从1开始遍历
        for(int i = 1; i < n; i++){
            // 搜索合适的更新位置，使用二分模板
            // 额外引入一个index来记录满足条件合法的值
            // 有的人的模板中，只有l和r两个变量，但是那个边界条件我总是记不住
            // 引入一个新的变量，个人感觉逻辑更明朗
            int l = 0, r = dp.size() - 1;
            int index = -1;
            while(l <= r){
                // mid这里用l加一半的形式，不容易溢出int
                int mid = l + (r - l) / 2;
                if(dp[mid] >= envelopes[i][1]){
                    // 我们要找的是dp数组中第一个大于等于当前h的位置
                    // 因此在这里更新index值
                    index = mid;
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            if(index == -1){
                dp.emplace_back(envelopes[i][1]);
            }
            else{
                dp[index] = envelopes[i][1];
            }
        }
        return dp.size();
    }
};

C++写到这里，差不多就是40-50 ms了，比方法一快了不老少，心满意足。

写在最后

延伸扩展问题

简化到一维：300. 最长递增子序列
扩展到三维：面试题 08.13. 堆箱子

加油熹熹坨坨！

给阿熹的鼓劲儿！

354. 俄罗斯套娃信封问题（禁止套娃！）

方法一：比较暴力的动态规划

思路

复杂度分析

快乐小视频

具体代码：

方法二：第二维参与排序

思路

复杂度分析

快乐小视频

具体代码

方法三：维护单增序列

思路

复杂度分析

快乐小视频

具体代码

方法四：二分查找

思路

复杂度分析

快乐小视频

具体代码

写在最后

延伸扩展问题

加油熹熹坨坨！

猜你喜欢

热点阅读