最长递增子序列的变种：俄罗斯套娃信封问题（二维LIS） 题目描述 给定一些信封，每个信封用一对整数 (w, h) 表示，分别代表信封的宽度和高度。当一个信封的宽度和高度都大于另一个信封时，较小的信封可以放入较大的信封内，如同俄罗斯套娃一样。计算最多能嵌套多少层信封。 注意：信封不能旋转，即不能交换宽度和高度。 示例 输入： envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出： 3 解释：最多嵌套的信封序列为 [2,3] → [5,4] → [6,7] （或 [2,3] → [6,4] → [6,7] ）。 解题思路 此问题可转化为二维的最长递增子序列（LIS）问题。关键步骤是 对信封排序 ，然后 在高度序列上求LIS ，但需避免宽度相同的信封被重复嵌套。 步骤详解 排序预处理 首先按宽度 w 升序排序，这样后续只需关注高度的递增关系。 关键技巧 ：若两个信封宽度相同，则按高度 h 降序排序。为什么？ 因为宽度相同的信封无法相互嵌套，通过高度降序可避免在LIS中选取多个宽度相同的信封（例如 [6,4] 和 [6,7] 不会同时出现在序列中）。 示例排序后： [[2,3], [5,4], [6,7], [6,4]] （宽度相同时， [6,7] 排在 [6,4] 前，防止 [6,4] 和 [6,7] 同时被选） 提取高度序列并求LIS 从排序后的信封中提取高度序列： [3, 4, 7, 4] 。 问题转化为：在高度序列上求最长递增子序列的长度。 使用 贪心+二分查找 的LIS算法（时间复杂度O(n log n)）： 维护一个数组 dp ，表示长度为 i+1 的递增子序列的最小末尾值。 遍历每个高度 h ： 若 h 大于 dp 中所有元素，则将其加入末尾（子序列长度+1）。 否则，用 h 替换 dp 中第一个大于或等于 h 的数（保持 dp 的单调性）。 LIS过程模拟 高度序列： [3, 4, 7, 4] h=3 ： dp = [3] h=4 ：大于3，扩展→ dp = [3,4] h=7 ：大于4，扩展→ dp = [3,4,7] h=4 ：替换第一个≥4的数（即4）→ dp = [3,4,7] （不变，但若序列为 [3,5,4] 则会更新） 最终 dp 的长度为3，即答案。 算法实现要点 排序： sort(envelopes, (a,b) => a[0] != b[0] ? a[0]-b[0] : b[1]-a[1]) LIS：遍历高度，用二分查找维护 dp 数组。 复杂度分析 排序：O(n log n) LIS：O(n log n) 总复杂度：O(n log n) 总结 通过排序将二维问题降为一维，再应用高效的LIS算法，是解决此类“嵌套”问题的经典思路。排序时对相同宽度的信封按高度降序，是避免错误嵌套的关键。