俄罗斯套娃信封问题 图解题解
这道题到底在问什么
- 输入
- envelopes=[[5,4],[6,4],[6,7],[2,3]]
- 输出
- 3([2,3] 套 [5,4] 套 [6,7])
- 输入
- envelopes=[[1,1],[1,1],[1,1]]
- 输出
- 1(宽高相同不能互套)
最优解：一步一步想明白
- 3记住「宽升高降排序 → 高度求严格 LIS → tails 二分(末尾 append、否则替换)」,下面逐步套它。
- 4先排序。注意宽都为 6 的两个信封 [6,8] 排在 [6,7] 前面(高降序):这样它俩的高 8、7 在后面不会形成递增,避免把同宽的错当成能互套。
- 5抽出排序后的高度序列 [3, 5, 8, 7, 4, 5]。问题已降成一维:在这串高度里找最长严格递增子序列的长度。
- 6准备 tails 数组(初始空)。它不是真正的子序列,而是「每种长度的递增链所能达到的最小结尾」,用来给后续高度快速找接入点。
- 7回到高度序列。前面 0 个已处理(蓝),现在看第 1 个高度 3(紫)。把它拿去更新 tails。
- 8轮到高度 3。在 tails=[空] 里二分查第一个不小于 3 的位置,得到 i=0。
- 9i 落在末尾,说明 3 能接到当前最长链后面,append。tails 变长,LIS 长度增到 1。
- 10回到高度序列。前面 1 个已处理(蓝),现在看第 2 个高度 5(紫)。把它拿去更新 tails。
- 11轮到高度 5。在 tails=[3] 里二分查第一个不小于 5 的位置,得到 i=1。
- 12i 落在末尾,说明 5 能接到当前最长链后面,append。tails 变长,LIS 长度增到 2。
- 13回到高度序列。前面 2 个已处理(蓝),现在看第 3 个高度 8(紫)。把它拿去更新 tails。
- 14轮到高度 8。在 tails=[3, 5] 里二分查第一个不小于 8 的位置,得到 i=2。
- 15i 落在末尾,说明 8 能接到当前最长链后面,append。tails 变长,LIS 长度增到 3。
- 16回到高度序列。前面 3 个已处理(蓝),现在看第 4 个高度 7(紫)。把它拿去更新 tails。
- 17轮到高度 7。在 tails=[3, 5, 8] 里二分查第一个不小于 7 的位置,得到 i=2。
- 18i 在中间,用 7 替换 tails[2] 原来的 8:让长度 3 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。
- 19回到高度序列。前面 4 个已处理(蓝),现在看第 5 个高度 4(紫)。把它拿去更新 tails。
- 20轮到高度 4。在 tails=[3, 5, 7] 里二分查第一个不小于 4 的位置,得到 i=1。
- 21i 在中间,用 4 替换 tails[1] 原来的 5:让长度 2 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。
- 22回到高度序列。前面 5 个已处理(蓝),现在看第 6 个高度 5(紫)。把它拿去更新 tails。
- 23轮到高度 5。在 tails=[3, 4, 7] 里二分查第一个不小于 5 的位置,得到 i=2。
- 24i 在中间,用 5 替换 tails[2] 原来的 7:让长度 3 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。
- 25全部处理完,tails 长度 = 3,就是高度序列的最长严格递增子序列长度,也就是最多能套娃的信封数 3。注意 tails 本身的值 [3, 4, 5] 不一定是真实的那条链,但它的「长度」一定正确。
⚠️ 容易写错的地方
✗ 错：宽相同的按高升序排
✓ 对：宽相同必须按高降序排
若同宽按高升序,后面更大的高会被错当成可递增、把两个同宽信封算进一条链;高降序让同宽的高不递增,自然排除
✗ 错：在 LIS 里用「≤」当递增
✓ 对：套娃要求严格小于,用严格递增
宽高都要严格小于才能套;tails 二分用 lower_bound(第一个 ≥ h)对应严格递增,用 upper_bound 会错算成非严格
✗ 错：以为 tails 就是那条最长链
✓ 对：tails 只保证长度对,值未必是真实链
替换操作会让 tails 的值不构成实际子序列,但「长度」始终等于 LIS 长度;要还原真实链需额外记录前驱
完整代码（Python / C++ / Java）
Python
from typing import List
from bisect import bisect_left
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
lis = []
for _, h in envelopes:
i = bisect_left(lis, h)
if i == len(lis):
lis.append(h)
else:
lis[i] = h
return len(lis)C++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), [](auto& a, auto& b){ return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]; });
vector<int> lis;
for (auto &e : envelopes) {
int h = e[1];
auto it = lower_bound(lis.begin(), lis.end(), h);
if (it == lis.end()) lis.push_back(h);
else *it = h;
}
return lis.size();
}
};Java
import java.util.*;
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a,b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int[] lis = new int[envelopes.length];
int size = 0;
for (int[] e : envelopes) {
int i = Arrays.binarySearch(lis, 0, size, e[1]);
if (i < 0) i = -i - 1;
lis[i] = e[1];
if (i == size) size++;
}
return size;
}
}复杂度
时间
O(n log n)
n 是信封数。排序 O(n log n);遍历每个高度做一次二分 O(log n),共 O(n log n);整体 O(n log n)
空间
O(n)
tails 数组最坏存 n 个高度,排序若用额外数组也是 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 俄罗斯套娃信封问题 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么可以把二维套娃问题降成一维的 LIS?+
排序后宽是从左到右不减的。固定这个顺序遍历,只要在高上找一条严格递增的子序列,这条子序列对应的信封宽也是「不减」的;再靠「同宽按高降序」排除掉宽相等的情况,就保证选出的相邻信封宽严格递增、高也严格递增,正好满足套娃条件。于是答案就是高度序列的最长严格递增子序列长度,二维降到一维。
tails + 二分的 O(n log n) LIS 和朴素 O(n²) 的 DP 有什么区别?+
朴素 LIS 用 dp[i]=以 i 结尾的最长链,需双重循环 O(n²)。tails 法维护「每种长度链的最小结尾」,它天然单调递增,所以新元素能用二分 O(log n) 找接入点,总复杂度 O(n log n)。代价是 tails 的值不再是真实子序列,只保证长度正确;若要还原具体那条链,需额外记每个元素的链长和前驱。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 俄罗斯套娃信封问题 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。