LeetCode 354：俄罗斯套娃信封问题（贪心算法）—

👋 欢迎阅读

🎯 欢迎来到「俄罗斯套娃信封问题」题解之旅！本文将带你从“套娃式的嵌套”这一直观需求出发，深入理解如何将二维最长递增子序列问题转化为一维 LIS，并掌握排序 + 最长递增子序列（LIS）的经典解法。

在开始之前，建议你先：

了解题目背景：这是 LeetCode 354 题，给定若干信封 [w, h]，一个信封能放入另一个当且仅当宽度和高度都严格大于，求最多能嵌套多少个信封（即最长链的长度）。本质上，这是一个二维偏序问题，可转化为对其中一维排序后，在另一维上求最长严格递增子序列。
明确学习目标：掌握核心转化技巧——先按宽度升序排列，若宽度相同则按高度降序排列（这样能避免宽度相等时错误嵌套），然后对高度数组求 LIS（严格递增）的长度。
准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如 envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出 3）。

本文将从问题转化（二维降一维）、排序策略设计、LIS 求解（DP 与贪心二分）到代码实现，层层递进。即使你对 LIS 还不熟悉，我们也会从“按宽度排好序后，只看高度怎么递增”这一直觉出发，让你轻松抓住核心思想——宽度排序去除了一个维度的约束，剩下只需在高度上找最长递增子序列，且相同宽度用降序避免错误嵌套。现在，让我们一起把信封一层层套起来，找出最长的套娃链吧！ 📨🪆

一、题目

354. 俄罗斯套娃信封问题 – 力扣（LeetCode）

二、做题思路

一、问题分析（前置分析）

给定一组信封 [w, h]，一个信封能放入另一个当且仅当宽度和高度都严格更小。要求计算最多能组成多少层套娃。

核心转化：这本质上是一个二维最长严格递增子序列问题。我们需要在宽度和高度两个维度上都找到严格递增的最长序列。

核心策略：先按宽度升序排序，当宽度相同时按高度降序排序，这样就将二维问题转化为对高度数组求一维最长严格递增子序列（LIS）。因为宽度升序保证了后一个信封的宽度一定 ≥ 前一个；而相同宽度下降序排列，则保证了同宽度的信封不会被错误地纳入同一个 LIS 中，从而满足“严格递增”的要求。

二、贪心策略（核心决策规则）

第一步：对 envelopes 排序：
- 按宽度升序排列；
- 若宽度相同，按高度降序排列。
第二步：提取排序后的高度序列，使用贪心 + 二分求最长严格递增子序列：
- 维护数组 ret，ret[i] 表示长度为 i+1 的递增子序列的最小末尾高度；
- 遍历高度 h：
  - 若 h > ret.back()，则追加到末尾；
  - 否则，用二分查找 ret 中第一个 >= h 的位置并替换为 h。
第三步：ret.size() 即为最多信封嵌套数。

三、正确性说明（简单版本）

排序策略：先按宽度升序，后按高度降序，使得在宽度相同的信封中，高度呈现降序，这样在后续求 LIS 时，相同宽度的信封不会同时出现在递增序列中（因为高度不会递增），从而保证了“严格递增”条件。然后只需要在高度序列上求 LIS，因为宽度已经有序，只要高度递增，就一定能形成合法的嵌套链。

四、实现细节（边界防护）

排序时使用 Lambda 表达式：return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
ret 数组初始化为第一个信封的高度。
遍历时，若 h > ret.back()，直接追加；否则用二分查找第一个 >= h 的位置并替换。
二分查找时，left 和 right 分别指向 ret 首尾，循环条件 left < right。
时间复杂度：排序 O(n log n)，LIS O(n log n)，总体 O(n log n)。
若 envelopes 为空，直接返回 0（但题目保证非空）。

五、返回值（目标映射）

返回 ret.size()，即最多能嵌套的信封数量。

四、代码

class Solution
{
public:
int maxEnvelopes(vector<vector<int>>& envelopes)
{
// 1. 排序策略：
// 将信封按宽度升序排列；若宽度相同，则按高度降序排列。
// 原因：在宽度相同时，降序排列能保证在后续求 LIS（最长严格递增子序列）时，
// 相同宽度的信封不会被错误地选入同一递增序列（因为高度降序后，相同宽度的信封高度不会递增）。
// 这保证了我们只需对高度数组求最长严格递增子序列，即可得到最多嵌套的信封数。
sort(envelopes.begin(), envelopes.end(), [&](const vector<int>& v1, const vector<int>& v2)
{
return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
});
// 2. LIS（最长递增子序列）问题：对排序后的信封高度序列，求最长严格递增子序列的长度。
// 使用贪心 + 二分优化：ret 数组存储长度为 i+1 的递增子序列的“最小末尾高度”。
vector<int> ret;
ret.push_back(envelopes[0][1]); // 初始以第一个信封的高度作为长度为1的序列末尾

// 3. 遍历剩余信封的高度
for (int i = 1; i < envelopes.size(); i++)
{
int b = envelopes[i][1]; // 当前信封的高度

// 如果当前高度大于 ret 的末尾，则可以直接追加，形成更长的递增序列
if (b > ret.back())
{
ret.push_back(b);
}
else
{
// 否则，在 ret 中找到第一个 >= b 的位置，替换为 b（贪心策略：让末尾尽可能小）
int left = 0, right = ret.size() – 1;
while (left < right)
{
int mid = (left + right) / 2;
if (ret[mid] >= b)
{
right = mid; // 向左搜索（因为 mid 可能满足条件）
}
else
{
left = mid + 1; // 向右搜索
}
}
// 此时 left == right，且指向第一个 >= b 的位置
ret[left] = b;
}
}

// 4. ret 的大小即为最长严格递增子序列的长度，也就是最多能嵌套的信封数量
return ret.size();
}
};

五、流程图

六、正确性说明（详细版）

步骤 1：符号与问题建模

排序策略：宽度升序，宽度相同时高度降序，这样相同宽度的信封高度不会递增，从而保证在高度序列上求严格递增子序列时，不会同时选中两个相同宽度的信封。
LIS 贪心：维护一个数组 tails，其长度即为当前最长递增子序列长度，每个位置存储该长度下的最小末尾高度。遍历高度时，通过二分更新，保证 tails 始终最优。

步骤 2：关键性质 —— 排序转换的正确性与 LIS 贪心的最优性

详细论证：

性质1（排序转换）：任何合法的嵌套序列，其宽度必须严格递增，因此按宽度排序后，嵌套序列对应一个子序列。若宽度相同，则高度必须严格递增，但由于排序时同宽高度降序，相同宽度的信封在高度序列中不可能形成递增，所以 LIS 不会包含它们。反之，若高度序列有一个严格递增子序列，其对应的宽度也是非递减的，但同宽高度降序保证了宽度相等时高度不增，因此宽度也必然严格递增，所以这些信封可以嵌套。因此原问题精确等价于对排序后的高度序列求 LIS。
性质2（LIS 贪心替换）：对于高度 h，若 h > tails.back()，则当前最长序列可以延长，追加 h 是唯一能增加长度的方式，贪心正确。若 h ≤ tails.back()，则 h 不能延长最长序列，但可以优化某个较短长度的最小末尾。通过二分找到第一个 ≥ h 的位置 pos，将 tails[pos] 替换为 h。因为 h 更小，该长度的最小末尾变小，且不破坏 tails 的单调性，这样后续更有可能被扩展，因此替换是安全且最优的。
性质3（单调性）：由 LIS 的定义和替换规则，tails 严格递增，因此可用二分查找。

步骤 3：归纳证明 —— 扫描过程得到全局最优 LIS 长度

详细论证：

归纳基础：第一个高度直接加入 tails，长度为1，且是长度为1的递增子序列的最小末尾，显然成立。
归纳步骤：假设处理完前 i 个高度后，tails 满足性质：tails[j] 是长度为 j+1 的递增子序列的最小末尾，且 tails 严格递增。现在处理第 i+1 个高度 h：
- 若 h > tails.back()，则当前最长长度 L 的序列末尾小于 h，可以接上 h 得到长度 L+1 的递增子序列，因此 tails.push_back(h) 是正确且必须的，因为这延长了 LIS。
- 若 h ≤ tails.back()，则 h 不能延长最长序列，但可以优化某个较短长度的末尾。二分找到第一个 ≥ h 的位置 pos，因为 tails[pos] 是第一个不小于 h 的，替换为 h 后，tails 仍严格递增，且该长度的最小末尾变小，不会影响其他长度，因此归纳假设仍然成立。
终止：遍历完所有高度后，tails 长度等于前 n 个高度的 LIS 长度。由性质1，该长度即为原问题的最多嵌套信封数。因为每一步的贪心选择都证明是强制或最优的，所以结果全局最优。

🎯 闭幕

动态规划学习路径图

🎉 恭喜你完成了「俄罗斯套娃信封问题」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀 动手实践在 LeetCode 上提交代码，尝试不同的测试用例。

💡 深入思考

本题的核心是将问题转化为最长递增子序列（LIS）。排序时，宽度升序，宽度相同时高度降序。为什么要对相同宽度的信封按高度降序排列？如果改为升序，会怎样影响 LIS 的结果？请举例说明。
求高度序列的 LIS 时，代码使用了贪心 + 二分优化。ret 数组存储长度为 i+1 的递增子序列的最小末尾高度。为什么每次遇到更大的高度直接追加，否则替换第一个 ≥ 该高度的位置，能保证最终长度正确？这种替换会不会破坏原序列的连续性？
排序后，为什么只对高度做 LIS 就能得到答案，而不需要再检查宽度？排序是否完全消除了宽度对嵌套的限制？

📚 延伸挑战

如果信封可以旋转（即宽高可以互换），排序前需要如何处理？规则会变得更复杂吗？

如果你觉得本文对你有所帮助，欢迎：

👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨

LeetCode 354：俄罗斯套娃信封问题（贪心算法）—— 题解

👋 欢迎阅读

一、题目