354. 俄罗斯套娃信封问题
考点
- LIS
- 排序优化
思路
一、问题抽象与形式化描述
给定 \(n\) 个信封，每个信封由一对整数表示： \[ (w_i, h_i) \] 其中 \(w_i\) 为宽度，\(h_i\) 为高度。
若存在一组信封序列 \[ (w_{i_1}, h_{i_1}), (w_{i_2}, h_{i_2}), \dots, (w_{i_k}, h_{i_k}) \] 满足 \[ w_{i_1} < w_{i_2} < \dots < w_{i_k}, \quad h_{i_1} < h_{i_2} < \dots < h_{i_k}, \] 则称该序列可以形成一组“俄罗斯套娃”。
目标：求满足上述条件的最长序列长度。
二、二维严格递增问题的本质困难
该问题本质是一个 二维偏序集上的最长链问题：
- 宽度必须严格递增
- 高度必须严格递增
直接进行二维 DP： \[ dp[i] = \max_{j<i,\ w_j<w_i,\ h_j<h_i} (dp[j]+1) \] 时间复杂度为 \(O(n^2)\)，在 \(n \le 10^5\) 的约束下不可行。
因此，必须通过结构性重排（排序）将二维约束降维。
三、核心思想：通过排序消去一个维度
3.1 排序的目标
排序的目的并非“整理数据”，而是：
人为制造一个“单调扫描顺序”，使其中一个严格条件自动成立
如果信封按宽度 \(w\) 排序，那么在扫描顺序中： \[ w_1 \le w_2 \le \dots \le w_n \] 此时，宽度条件已被部分满足，问题转化为：
在满足宽度顺序的前提下，寻找高度的最长严格递增子序列（LIS）
但这里隐藏着一个关键陷阱。
四、排序设计中的核心陷阱与优化
4.1 错误的直觉：双关键字同时升序
若使用排序规则： \[ (w \uparrow,\ h \uparrow) \] 则对于同宽信封： \[ (w, h_1), (w, h_2), \quad h_1 < h_2 \] 在 LIS 过程中，高度序列是递增的，算法会错误地将它们同时选入。
然而这违反了问题的严格宽度递增条件： \[ w \not< w \] 结论：
同宽信封在 LIS 阶段必须被强制“互斥”。
4.2 关键优化：同宽高度逆序排序
正确的排序策略是： \[ \boxed{ \text{宽度 } w \text{ 升序，若 } w \text{ 相同，则高度 } h \text{ 降序} } \] 形式化写为： \[ (w_i < w_j) \ \lor\ (w_i = w_j \land h_i > h_j) \]
直观解释
- 宽度升序：保证扫描顺序中宽度不下降
- 同宽高度降序：破坏高度的递增性
于是对于同宽信封： \[ (w, 5), (w, 4), (w, 3) \] 高度序列是严格递减的，LIS 不可能选中多个。
4.3 这一设计的数学意义
排序后得到的序列满足：
- 任意被 LIS 同时选中的两个元素 \(i < j\)，必然有 \[ w_i < w_j \] （因为若 \(w_i = w_j\)，则 \(h_i > h_j\)，无法递增）
因此：
在高度上做 LIS，即等价于在二维条件下做最长合法嵌套序列
这一步是整个算法正确性的核心。
五、降维后的算法流程
5.1 排序
1 | sort(envelopes.begin(), envelopes.end(), tmp()); |
排序规则：
a[0] < b[0]- 若相等，
a[1] > b[1]
5.2 在高度序列上求 LIS（O(n log n)）
定义数组： \[ f[k] = \text{长度为 } k+1 \text{ 的严格递增子序列的最小结尾高度} \] 对每个高度 \(h\)：
- 在 \(f\) 中二分查找第一个 \(\ge h\) 的位置
- 用 \(h\) 覆盖该位置（或扩展数组）
1 | auto it = lower_bound(f.begin(), f.end(), h); |
使用 lower_bound 的原因是：
- 要求 严格递增
- 相等高度不允许扩展序列
六、完整算法正确性总结
该算法正确性的三层保证：
- 排序阶段
- 宽度升序：消除宽度回退
- 同宽高度降序：消除非法同宽嵌套
- LIS 阶段
- 只在高度上判断严格递增
- 自动保证宽度也严格递增
- 复杂度
- 排序：\(O(n \log n)\)
- LIS：\(O(n \log n)\)
- 总复杂度：\(O(n \log n)\)
七、AC代码
1 | class Solution { |