LC 354. 俄罗斯套娃信封问题
题目描述
这是 LeetCode 上的 354. 俄罗斯套娃信封问题 ,难度为 困难。
给你一个二维整数数组 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 <= $10^4$
动态规划
这是一道经典的 DP 模型题目:最长上升子序列(LIS)。
首先我们先对 envelopes
进行排序,确保信封是从小到大进行排序。
问题就转化为我们从这个序列中选择 k
个信封形成新的序列,使得新序列中的每个信封都能严格覆盖前面的信封(宽高都严格大于)。
我们可以定义状态 $f[i]$ 为考虑前 i 个物品,并以第 $i$ 个物品为结尾的最大值。
对于每个$f[i]$ 而言,最小值为 $1$,代表只选择自己一个信封。
那么对于一般的 $f[i]$ 该如何求解呢?因为第 i 件物品是必须选择的。我们可以枚举前面的 $i - 1$ 件物品,哪一件可以作为第 $i$ 件物品的上一件物品。
在前 $i - 1$ 件物品中只要有符合条件的,我们就使用 $max(f[i], f[j] + 1)$ 更新 $f[i]$。
然后在所有方案中取一个 max
即是答案。
代码:
1 |
|
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(n)$
二分 + 动态规划
上述方案其实算是一个朴素方案,复杂度是 $O(n^2)$ 的,也是我最先想到思路,但是题目没有给出数据范围,也不知道能不能过。
唯唯诺诺交了一个居然过了。
下面讲下其他优化解法。
首先还是和之前一样,我们可以通过复杂度分析来想优化方向。
指数算法往下优化就是对数解法或者线性解法。
仔细观察朴素解法,其实可优化的地方主要就是找第 $i$ 件物品的前一件物品的过程。
如果想要加快这个查找过程,我们需要使用某种数据结构进行记录。
并且是边迭代边更新数据结构里面的内容。
首先因为我们对 w
进行了排序(从小到大),然后迭代也是从前往后进行,因此我们只需要保证迭代过程中,对于 w
相同的数据不更新,就能保证 g
中只会出现满足 w
条件的信封。
到这一步,还需要用到的东西有两个:一个是 h
,因为只有 w
和 h
都同时满足,我们才能加入上升序列中;一个是信封所对应的上升序列长度,这是我们加速查找的核心。
我们使用数组 g
来记录,$g[i]$ 表示长度为 $i$ 的最长上升子序列的中的最小「信封高度」,同时需要使用 len
记录当前记录到的最大长度。
还是不理解?没关系,我们可以直接看看代码,我把基本逻辑写在了注释当中(你的重点应该落在对 $g[]$ 数组的理解上)。
代码:
1 |
|
- 时间复杂度:对于每件物品都是通过「二分」找到其前一件物品。复杂度为 $O(n\log{n})$
- 空间复杂度:$O(n)$
证明
我们可以这样做的前提是 g
数组具有二段性,可以通过证明其具有「单调性」来实现。
当然这里指的是 g
被使用的部分,也就是 $[0, len - 1]$ 的部分。
我们再回顾一下 g[]
数组的定义:$g[i]$ 表示长度为 $i$ 的最长上升子序列的中的最小「信封高度」
例如 $g[] = [0, 3, 4, 5]$ 代表的含义是:
- 上升序列长度为 0 的最小历史信封高度为 0
- 上升序列长度为 1 的最小历史信封高度为 3
- 上升序列长度为 2 的最小历史信封高度为 4
- 上升序列长度为 3 的最小历史信封高度为 5
可以通过反证法来证明其单调性:
假设 $g[]$ 不具有单调性,即至少有 $g[i] > g[j]$ ( $i < j$,令 $a = g[i]$, $b = g[j]$)
显然与我们的处理逻辑冲突。因为如果考虑一个「最小高度」为 b
的信封能够凑出长度为 j
的上升序列,自然也能凑出比 j
短的上升序列,对吧?
举个🌰,我们有信封:[[1,1],[2,2],[3,3],[4,4],[5,5]],我们能凑出很多种长度为 2 的上升序列方案,其中最小的方案是高度最小的方案是 [[1,1],[2,2]]。因此这时候 g[2] = 2,代表能凑出长度为 2 的上升序列所 必须使用的信封 的最小高度为 2。
这时候反过来考虑,如果使用 [2,2] 能够凑出长度为 2 的上升序列,必然也能凑出长度为 1 的上升序列(删除前面的其他信封即可)。
推而广之,如果我们有 $g[j] = b$,也就是凑成长度为 j
必须使用的最小信封高度为 b。那么我必然能够保留高度为 b
的信封,删掉上升序列中的一些信封,凑成任意长度比 j
小的上升序列。
综上,$g[i] > g[j](i < j)$ 与处理逻辑冲突,$g[]$ 数组为严格单调上升数组。
既然 $g[]$ 具有单调性,我们可以通过「二分」找到恰满足 check 条件的最大下标(最大下标达标表示最长上升序列长度)。
树状数组 + 动态规划
在「二分 + 动态规划」的解法中,我们通过「二分」来优化找第 $i$ 个文件的前一个文件过程。
这个过程同样能通过「树状数组」来实现。
首先仍然是对 w
进行排序,然后使用「树状数组」来维护 h 维度的前缀最大值。
对于 h
的高度,我们只关心多个信封之间的大小关系,而不关心具体相差多少,我们需要对 h
进行离散化。
通常使用「树状数组」都需要进行离散化,尤其是这里我们本身就要使用 $O(n)$ 的空间来存储 dp 值。
代码:
1 |
|
- 时间复杂度:处理每个物品时更新「树状数组」复杂度为$O(\log{n})$。整体复杂度为 $O(n\log{n})$
- 空间复杂度:$O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.354
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!