LeetCode 354. 俄罗斯套娃信封问题
题目描述
题意分析
每个信封由宽度和高度描述，只有内层的宽、高都严格小于外层，才能放入。求最多能嵌套多少个信封，返回数量，不需要给出具体链条。
可以重新安排信封顺序，但不允许旋转某个信封来交换宽高。宽度相同或高度相同都不能互相嵌套，重复信封也不能凭数量直接叠进同一条链。
解法：宽升高降排序 + 高度 LIS
核心思路
[!blue]
一条合法嵌套链的宽和高都严格递增。先按宽度升序排列，就可以把宽度条件交给顺序处理，再在高度上寻找严格递增子序列。但同宽信封的顺序必须特殊处理，否则高度上升可能被误当成可以继续嵌套。
对同宽信封按高度降序排列。这样任何严格递增的高度子序列都不可能同时取到两个同宽信封，因为同一宽度组中，后面的高度不会更大。反过来，任何合法嵌套链宽度都严格递增，排序后仍保持其先后关系，高度也仍递增。因此排序后的高度 LIS 与原问题的最长嵌套链完全对应。
求高度 LIS 时，令
tails[len - 1]表示已经扫描过的信封中，长度为len的递增子序列能够达到的最小结尾高度。长度相同时，结尾越小，后面能接上的高度范围就越大，因此只需保留这个最有利的结尾，不必保存每一条候选链。
tails本身严格递增：长度多一的合法序列，末尾一定大于它前面那段序列的末尾，而较短长度的最小末尾只会更小。对当前高度height，二分找到第一个大于等于它的位置p。若p > 0，前一个状态严格小于当前高度，所以存在长度为p的序列可以接上它，得到长度p + 1；把tails[p]更新为更小或相等的当前值，会使这个长度的未来选择更宽松。若所有结尾都小于当前高度，二分落在有效区间末尾，说明当前信封可以接到最长链后面，答案长度增加一；否则只改善同长度结尾，不改变已经达到的最大长度。相等高度会落在原位置并覆盖，不会增长，从而保留严格递增要求。
不同长度的最小结尾可能分别来自不同历史链条，因此
tails的整段内容未必就是一条实际嵌套链。这里仅求最大数量，保留它的有效长度已经足够。
解题步骤
- 将信封按宽度升序排序；宽度相同时，高度降序。排序会调整输入数组的顺序。
- 初始化空的最小结尾状态，依次读取排序后每个信封的高度。
- 在当前有效
tails区间中二分第一个大于等于当前高度的位置。- 用当前高度更新该位置；若位置恰好位于末尾，则新增一个状态，让最长长度增加一。
- 全部高度处理结束后，返回有效状态数量。
代码实现
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)$，最小结尾数组最多保存
n个高度，计入标准库排序也不超过该级别。
关键点总结
[!green]
- 宽升序、高度同宽降序，才能把两个严格维度正确归约为高度 LIS。
- 每个长度保留最小结尾，表示最容易被后续信封延长的候选状态。
- 二分找第一个大于等于当前高度的位置，相等只能覆盖，不能延长。
- 结尾状态用于求长度，不承担恢复具体嵌套方案的职责。
易错点总结
[!yellow]
- 同宽也按高度升序，可能让高度 LIS 同时选中多个实际上不能嵌套的信封。
- 随意交换每个信封的宽和高，相当于允许旋转，改变了题目约束。
- 查找第一个严格大于当前高度的位置，会把相等高度放到后面，错误允许非严格增长。
- 用二分覆盖次数或已处理信封数作为答案，混淆了改善某个结尾与延长整条链。
- 将
tails直接当成一条真实链输出，忽略了不同长度状态可能来自不同历史序列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 宽度排序后转成高度LIS；等宽按高度降序，防止把同宽信封错误连在一起。 |
| 646. 最长数对链 | 中等 | 同样先排序后选择可衔接的二元对象，但数对链要求前一个终点小于后一个起点，非二维严格包含。 |
| 673. 最长递增子序列的个数 | 中等 | 用以当前元素结尾的递增状态或最小尾值优化；本题先处理二维排序及等宽冲突，该题同时记录最优长度与达到该长度的方案数。 |