百亿私募笔试真题|俄罗斯套娃信封:排序 + 二分查找解决二维嵌套问题
- 2026-10-20 01:21:23
一、题目描述
给你一个二维整数数组 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 = []逐一处理：
[3] | ||
[3,4] | ||
[3,4,7] | ||
[3,4,7] |
最终：
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)
六、总结与思考
整个过程可以概括为：
二维嵌套问题 → 特殊排序 → 一维最长严格递增子序列 → 二分查找优化。
其中有三个关键点：
排序消除一个维度。 通过宽度升序排列，使我们只需要进一步考虑高度的递增关系。 相同宽度时，高度必须降序。 这样才能避免错误地把宽度相同的信封加入同一条嵌套链。 通过维护最小结尾值优化 LIS。 利用二分查找替代线性查找，将时间复杂度从 O(n²) 优化到 O(n log n)。
从算法学习的角度来看，这道题很有代表性。
很多看起来涉及多个维度、需要大量比较的问题，都可以先思考：能否通过排序固定其中一个维度，再将剩余部分转化为经典的一维算法问题？
