题目描述
思路解析
一句话答案：LeetCode 354 俄罗斯套娃信封是二维最长递增子序列（LIS）：先按宽升序排、同宽再按高降序排，把套娃降成对高度求严格递增子序列，同宽高降序专防同宽被误当能互套，用二分维护 lis 数组做到 O(n log n)、空间 O(n)。
俄罗斯套娃信封，这道题在挑什么
给一组信封，每项 [宽, 高]。一个要装进另一个，宽和高都得严格小于对方，有一边相等就套不进。问最多能套几层。题面 [[5,4],[6,4],[6,7],[2,3]]，[2,3] 塞进 [5,4]、[5,4] 塞进 [6,7]，套成 3 个。宽或高相等的彼此套不了，是全题的机关。
两两试套，为什么会慢到跑不完
n 个信封两两配对看能不能套只是 O(n²)，可真要穷举挑哪几个连成一串，每个选或不选分两条岔，2ⁿ 条组合枚举不完，还大半在重算同一段前缀。先把信封排好序、让谁能接谁有方向，指数枚举就收拢成一趟从左到右的递推（拿前面算好的结果往后推），开销靠这步压下来。
同宽的信封，为什么要按高从大到小排
排序规矩两条：宽从小到大，宽一样时高从大到小。第一条好懂：宽不减，套娃链才不回头。第二条才绕：宽相等的两个信封永远套不进彼此（宽得严格更小），可同宽若按高升序排，它俩的高一小一大、像能接上的递增对，求递增链时就被当成能套。改成高降序，同宽的高一路往下、绝不递增，链里最多挑一个，同宽误套被排序堵死。题面 [6,7]、[6,4] 同宽，排成先 7 后 4 正是这用意。
排完这列高度，套娃怎么就成了 LIS
排好序后宽已从小到大、不回头，只要在高上找一条严格变大的挑法，对应那串信封宽不减、高严格增，就能一个个套起来。二维套娃塌成一维：求高度序列的最长严格递增子序列（LIS，最长的一个个变大、可跳着挑的子序列）。
O(n log n) 的快法：开一个 lis 数组，存的不是真链，而是『各长度的递增链能达到的最小结尾』。每来一个高度 h，用二分（Python 的 bisect_left，对半砍找位置）在 lis 里找第一个不小于 h 的位置：落末尾说明 h 比所有结尾都大、能把最长链接长一节，链变长；落中间就用 h 替换那位置原值，把这档链结尾压小、日后更易接长。
拿题面那四个信封，亲手把 lis 填出来
拿题面 [[5,4],[6,4],[6,7],[2,3]] 走一遍。按『宽升、同宽高降』排成 [2,3]、[5,4]、[6,7]、[6,4]，抽出高度 [3,4,7,4]，lis 起初空。前三个 3、4、7 一个比一个大，二分都落末尾、依次接上成 [3,4,7]。最后的 4：找第一个不小于 4 的位置是 1（值正好 4），落中间，用 4 替换原来的 4，lis 仍 [3,4,7]、长度不变。走完长度 3，答案 3，即 [2,3] 套 [5,4] 套 [6,7]。
二分若改找第一个比 h 大的位置，答案为什么会偏大
二分若改成找『第一个比 h 大』，等高的高度会被接到链尾而非替换，两个等高信封就被当成能递增互套，答案凭空偏大——严格递增全靠『不小于』守住：等高触发替换、不接长。开销：排序 O(n log n)，每个高度一次二分、合计 O(n log n)，lis 最多装 n 个、空间 O(n)。两个边界：单个信封链长 1；题面 [[1,1],[1,1],[1,1]] 宽高全同，排完高度 [1,1,1]，只第一个接成 [1]、其余替换，答案 1。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「宽升高降排序 → 高度求严格 LIS → tails 二分(末尾 append、否则替换)」,下面逐步套它。
先排序。注意宽都为 6 的两个信封 [6,8] 排在 [6,7] 前面(高降序):这样它俩的高 8、7 在后面不会形成递增,避免把同宽的错当成能互套。
抽出排序后的高度序列 [3, 5, 8, 7, 4, 5]。问题已降成一维:在这串高度里找最长严格递增子序列的长度。
准备 tails 数组(初始空)。它不是真正的子序列,而是「每种长度的递增链所能达到的最小结尾」,用来给后续高度快速找接入点。
回到高度序列。前面 0 个已处理(蓝),现在看第 1 个高度 3(紫)。把它拿去更新 tails。
轮到高度 3。在 tails=[空] 里二分查第一个不小于 3 的位置,得到 i=0。
i 落在末尾,说明 3 能接到当前最长链后面,append。tails 变长,LIS 长度增到 1。
回到高度序列。前面 1 个已处理(蓝),现在看第 2 个高度 5(紫)。把它拿去更新 tails。
轮到高度 5。在 tails=[3] 里二分查第一个不小于 5 的位置,得到 i=1。
i 落在末尾,说明 5 能接到当前最长链后面,append。tails 变长,LIS 长度增到 2。
回到高度序列。前面 2 个已处理(蓝),现在看第 3 个高度 8(紫)。把它拿去更新 tails。
轮到高度 8。在 tails=[3, 5] 里二分查第一个不小于 8 的位置,得到 i=2。
i 落在末尾,说明 8 能接到当前最长链后面,append。tails 变长,LIS 长度增到 3。
回到高度序列。前面 3 个已处理(蓝),现在看第 4 个高度 7(紫)。把它拿去更新 tails。
轮到高度 7。在 tails=[3, 5, 8] 里二分查第一个不小于 7 的位置,得到 i=2。
i 在中间,用 7 替换 tails[2] 原来的 8:让长度 3 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。
回到高度序列。前面 4 个已处理(蓝),现在看第 5 个高度 4(紫)。把它拿去更新 tails。
轮到高度 4。在 tails=[3, 5, 7] 里二分查第一个不小于 4 的位置,得到 i=1。
i 在中间,用 4 替换 tails[1] 原来的 5:让长度 2 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。
回到高度序列。前面 5 个已处理(蓝),现在看第 6 个高度 5(紫)。把它拿去更新 tails。
轮到高度 5。在 tails=[3, 4, 7] 里二分查第一个不小于 5 的位置,得到 i=2。
i 在中间,用 5 替换 tails[2] 原来的 7:让长度 3 的链结尾更小,日后更容易接长。LIS 长度暂不变(仍 3)。
全部处理完,tails 长度 = 3,就是高度序列的最长严格递增子序列长度,也就是最多能套娃的信封数 3。注意 tails 本身的值 [3, 4, 5] 不一定是真实的那条链,但它的「长度」一定正确。
边界:单信封 1;全相同 1;同宽不同高也只 1。
两个延伸:排序把二维降一维;tails 二分把 LIS 从 O(n²) 提到 O(n log n)。
参考代码
from typing import Listfrom bisect import bisect_leftclass 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)复杂度
- 时间：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)
易错点
面试追问把动画讲成自己的话
追问为什么可以把二维套娃问题降成一维的 LIS?
追问tails + 二分的 O(n log n) LIS 和朴素 O(n²) 的 DP 有什么区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
青蛙过河
LeetCode 403 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题