LeetCode 354. 俄罗斯套娃信封问题
目录
题目描述
题意分析
每个信封给出宽和高两个数，一个信封能装进另一个的条件是宽和高都严格大于对方。注意是「严格大于」而不是「大于等于」：宽 5 高 4 的信封装不进宽 5 高 6 的信封，因为宽度只是相等；宽高完全相同的两个信封也永远互不相容。要求的是最多能套出多长的一条嵌套链，信封可以任意重排，不必按输入顺序。
这里的核心难点在于二维偏序：每个信封有两个坐标，而「能嵌套」这个关系要求两个坐标同时严格变大。二维偏序不是全序——宽 3 高 9 和宽 8 高 2 谁也套不进谁，所以不能简单地排个序就一路贪心取下去。
约束信号：信封数量可达 $10^5$，宽高上限 $10^5$。$10^5$ 这个量级明确排除了 $O(n^2)$ 的两两比较写法，答案要落在 $O(n \log n)$ 上。
边界要留意三处：只有一个信封时答案是 1；所有信封宽度相同时答案也是 1，因为宽度没有严格变大；宽高完全重复的信封只能算一个。
解法：宽升高降排序 + 高度 LIS
核心思路
直接做二维 DP 需要比较所有信封对，时间为 $O(n^2)$。要达到 $O(n \log n)$，先通过排序消除宽度这一维，再对高度求最长严格递增子序列（LIS）：
- 宽度升序；
- 宽度相同时，高度降序。
同宽高度降序是关键：严格递增的高度子序列不可能同时选中两个同宽信封。若同宽高度升序，LIS 会把本不能互相嵌套的信封错误连接起来。
排序后，用
tails[k]表示长度为k + 1的递增子序列所能取得的最小结尾高度。对每个高度二分找到第一个大于等于它的位置并覆盖；若不存在则追加。较小的结尾给后续信封留下更多选择，因此覆盖不会损失最优答案。等价性证明：任意高度严格递增的子序列不含同宽元素，所以宽、高都严格递增，构成合法嵌套链；任意合法链按宽度排序后仍保持原先顺序，其高度也严格递增。因此 LIS 的长度恰好是答案。
解题步骤
- 将信封按“宽升序、同宽高降序”排序。
- 依次读取高度，在
tails[0..size)中二分查找第一个大于等于当前高度的位置。- 覆盖该位置；若位置等于
size，说明当前高度可以延长最长链，令size++。- 扫描结束后返回
size。例如
[[5,4],[6,4],[6,7],[2,3]]排序后高度为[3,4,7,4]，tails依次变为[3]、[3,4]、[3,4,7]、[3,4,7]，答案为 3。
代码实现
import java.util.Arrays;
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (first, second) -> {
if (first[0] != second[0]) {
return Integer.compare(first[0], second[0]);
}
return Integer.compare(second[1], first[1]);
});
int[] tails = new int[envelopes.length];
int size = 0;
for (int[] envelope : envelopes) {
int height = envelope[1];
int left = 0;
int right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < height) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = height;
if (left == size) {
size++;
}
}
return size;
}
}
import "sort"
func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i int, j int) bool {
if envelopes[i][0] != envelopes[j][0] {
return envelopes[i][0] < envelopes[j][0]
}
return envelopes[i][1] > envelopes[j][1]
})
tails := make([]int, 0, len(envelopes))
for _, envelope := range envelopes {
height := envelope[1]
left, right := 0, len(tails)
for left < right {
mid := left + (right-left)/2
if tails[mid] < height {
left = mid + 1
} else {
right = mid
}
}
if left == len(tails) {
tails = append(tails, height)
} else {
tails[left] = height
}
}
return len(tails)
}
复杂度分析
- 时间复杂度：$O(n \log n)$。排序为 $O(n \log n)$，每个信封再进行一次 $O(\log n)$ 的二分。
- 空间复杂度：$O(n)$，
tails最多保存n个高度。
关键点总结
- 二维偏序降维的核心是“宽升高降”，同宽元素最多只能进入 LIS 一个。
- 严格递增 LIS 使用
lower_bound：寻找第一个大于等于当前高度的位置。tails只保存各长度的最小结尾，不一定是某条真实的嵌套链，但其长度就是答案。- Java 比较器使用
Integer.compare，避免用减法比较带来的溢出风险。
易错点总结
- 同宽若按高度升序，
[[1,1],[2,2],[2,3]]会被错误算成长度 3。- 二分若找第一个“大于”当前高度的位置，会把相等高度当作可延长，破坏严格递增要求。
right = size对应左闭右开区间，循环条件应为left < right。tails不能直接当成具体方案；若题目要求恢复链条，还需记录前驱和元素下标。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 一维 LIS 模板 |
| 368. 最大整除子集 | 中等 | 整除关系上的最长链 |
| 673. 最长递增子序列的个数 | 中等 | LIS 方案数统计 |
| 1048. 最长字符串链 | 中等 | 按长度分层建前驱链 |
| 面试题 08.13. 堆箱子 | 困难 | 三维严格递增堆叠 |
| 面试题 17.08. 马戏团人塔 | 中等 | 二维偏序降维求链长 |