百亿私募笔试真题|俄罗斯套娃信封:排序 + 二分查找解决二维嵌套问题

一、题目描述

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

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

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

注意： 不允许旋转信封。

示例 1：

输入：

envelopes = [[5,4],[6,4],[6,7],[2,3]]

输出：

3

解释：最多信封的个数为 3，组合为：

[2,3] → [5,4] → [6,7]

示例 2：

输入：

envelopes = [[1,1],[1,1],[1,1]]

输出：

1

解释：由于信封的宽度和高度都相同，无法互相嵌套，因此最多只能选择一个信封。

二、解题思路：如何将二维问题转化为一维问题？

1. 首先明确嵌套条件

设有两个信封：

• 信封 A：[w1, h1]
• 信封 B：[w2, h2]

要使 A 能够放入 B，必须同时满足：

w1 < w2h1 < h2

也就是说，宽度和高度都必须严格递增。

如果只有一个维度满足要求，或者某个维度相等，都不能完成嵌套。

因此，我们实际需要寻找的是：

一组宽度和高度都严格递增的信封，使其数量尽可能多。

2. 最直接的方法：动态规划

一种直观的思路是，先按照信封的宽度排序，然后通过动态规划，逐一判断前面的信封能否放入当前信封。

定义：

dp[i]：以第 i 个信封作为最外层信封时，最多能够嵌套的层数。

每个信封至少可以单独存在，因此初始化：

dp[i] = 1

对于排在当前信封前面的每个信封 j，如果同时满足：

w[j] < w[i] and h[j] < h[i]

则可以更新：

dp[i] = max(dp[i], dp[j] + 1)

最终答案为 max(dp)。

这种方法需要通过双重循环比较信封，时间复杂度为 O(n²)。

它能够正确求解问题，但我们还可以进一步优化。

3. 关键优化：通过排序消除一个维度

仔细观察嵌套条件：

宽度和高度都必须严格递增。

那么，能否先通过排序处理宽度，只需要在剩下的高度序列中寻找递增关系？

答案是可以的。

我们采用以下排序规则：

第一关键字：宽度从小到大排序。

第二关键字：当宽度相同时，高度从大到小排序。

对应 Python 代码：

envelopes.sort(key=lambda x: (x[0], -x[1]))

以示例 1 为例。

原始数组：

[[5,4],[6,4],[6,7],[2,3]]

排序后：

[[2,3],[5,4],[6,7],[6,4]]

此时，信封的宽度已经按照从小到大的顺序排列。

接下来提取高度：

[3,4,7,4]

可以发现，其中存在一个严格递增子序列：

3 → 4 → 7

对应信封：

[2,3] → [5,4] → [6,7]

恰好能够嵌套 3 层。

这就引出了一个关键结论：

经过特定规则排序后，原来的二维嵌套问题，就可以转化为求高度序列的最长严格递增子序列。

4. 为什么宽度相同时，高度必须降序？

考虑两个信封：

[[6,4],[6,7]]

这两个信封的宽度相同，都为 6。

根据题目要求，即使第二个信封的高度更大，它们也无法互相嵌套。

假设我们直接按照宽度升序、高度升序排列：

[[6,4],[6,7]]

提取高度以后：

[4,7]

显然，4 → 7 是一个严格递增子序列。

如果直接计算 LIS，就会错误地认为这两个信封能够嵌套。

但如果在宽度相同时，让高度降序排列：

[[6,7],[6,4]]

那么高度序列变成：

[7,4]

此时，两者不可能同时出现在一个严格递增子序列中。

也就是说，高度降序能够排除宽度相同的非法嵌套情况。

因此，排序后任意选出的严格递增高度子序列，对应的信封宽度也必然严格递增。

至此，我们就完成了二维问题向一维问题的转化。

三、最长递增子序列（LIS）与二分查找

完成排序之后，问题变成：

给定一个高度序列，找到其中最长严格递增子序列的长度。

这就是经典的 LIS（Longest Increasing Subsequence）问题。

对于示例 1：

heights = [3,4,7,4]

最长严格递增子序列可以是：

[3,4,7]

长度为 3。

如果使用传统动态规划求解 LIS，时间复杂度仍然是 O(n²)。

为了进一步优化，我们可以结合贪心思想与二分查找，将其降低到 O(n log n)。

1. 定义 tails 数组

维护一个辅助数组：

tails = []

其中：

tails[i] 表示长度为 i+1 的严格递增子序列，能够达到的最小结尾值。

为什么需要维护最小结尾值？

因为对于两个长度相同的递增子序列，结尾越小，就越容易在后面接上新的、更大的元素。

例如：

序列 A：3 → 5序列 B：3 → 4

两者的长度都是 2，但序列 B 的结尾更小。

如果接下来出现数字 5，那么序列 B 可以继续延长，而序列 A 不能接上相等的 5。

因此，在递增子序列长度相同的情况下，我们应该尽可能让结尾元素更小。

2. 遍历高度序列

对于每一个高度 h，使用二分查找，在 tails 中找到第一个大于等于 h 的位置。

Python 提供了现成的函数：

from bisect import bisect_leftpos = bisect_left(tails, h)

随后分成两种情况。

情况一：当前高度大于 tails 中所有元素。

说明当前高度可以接在已有最长递增子序列的后面，使长度增加 1。

因此直接追加：

if pos == len(tails):    tails.append(h)

情况二：tails 中存在大于等于当前高度的元素。

此时无法延长当前最长长度，但可以用当前高度更新对应长度的最小结尾值：

else:    tails[pos] = h

这样既不改变已有的最长长度，又能为后续元素创造更好的延伸条件。

注意，这里的 tails 并不一定是一条真实的完整递增子序列，它保存的是每种子序列长度对应的最优结尾值。

但它的长度始终等于目前找到的 LIS 长度。

3. 通过示例理解整个过程

仍然使用高度序列：

[3,4,7,4]

初始：

tails = []

逐一处理：

最终：

tails = [3,4,7]

所以：

len(tails) = 3

也就是说，最多可以嵌套 3 个信封。

为什么要使用 bisect_left，而不是 bisect_right？

因为题目要求严格递增。

bisect_left 返回第一个大于等于目标值的位置，因此遇到相同高度时，会进行替换，而不是错误地增加序列长度。

四、Python 完整代码

下面是最终的 O(n log n) 解法：

from bisect import bisect_leftclass Solution:    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:        # 1. 宽度升序，宽度相同时高度降序        envelopes.sort(key=lambda x: (x[0], -x[1]))        # 2. 维护各长度递增子序列的最小结尾高度        tails = []        # 3. 遍历排序后每个信封的高度        for w, h in envelopes:            # 找到第一个大于等于当前高度的位置            pos = bisect_left(tails, h)            # 如果当前高度大于所有结尾值，则延长序列            if pos == len(tails):                tails.append(h)            # 否则更新对应长度的最小结尾高度            else:                tails[pos] = h        # 4. 返回最长严格递增子序列的长度        return len(tails)

五、时间复杂度与空间复杂度

设共有 n 个信封。

1. 时间复杂度：O(n log n)

整个算法主要包含两部分：

• 排序：对 n 个信封排序，时间复杂度为 O(n log n)。
• 二分查找：遍历 n 个信封，每次通过 bisect_left 进行 O(log n) 的查找，总复杂度为 O(n log n)。

因此，总时间复杂度为：

O(n log n)

相比传统动态规划的 O(n²)，效率得到了明显提升。

2. 空间复杂度：O(n)

算法额外使用 tails 数组，最多存储 n 个元素。

因此，额外空间复杂度为：

O(n)

六、总结与思考

整个过程可以概括为：

二维嵌套问题 → 特殊排序 → 一维最长严格递增子序列 → 二分查找优化。

其中有三个关键点：

1. 排序消除一个维度。 通过宽度升序排列，使我们只需要进一步考虑高度的递增关系。
2. 相同宽度时，高度必须降序。 这样才能避免错误地把宽度相同的信封加入同一条嵌套链。
3. 通过维护最小结尾值优化 LIS。 利用二分查找替代线性查找，将时间复杂度从 O(n²) 优化到 O(n log n)。

从算法学习的角度来看，这道题很有代表性。

很多看起来涉及多个维度、需要大量比较的问题，都可以先思考：能否通过排序固定其中一个维度，再将剩余部分转化为经典的一维算法问题？