最长递增子序列的变种：俄罗斯套娃信封问题（二维LIS） 题目描述 给定一些信封的宽度和高度对 envelopes = [[w1, h1], [w2, h2], ..., [wn, hn]] ，如果一个信封的宽度和高度都大于另一个信封，那么它可以套在另一个信封外面。请计算最多能套多少层信封（即最长递增子序列的长度，但这里是二维的）。 注意 ：信封不能旋转（即宽度和高度是固定的），且一个信封最多只能套一个信封。 示例 输入： envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出： 3 解释：最长嵌套序列是 [2,3] → [5,4] → [6,7] （或 [2,3] → [6,4] → [6,7] ）。 解题过程 步骤1：问题分析 这是一个二维的最长递增子序列（LIS）问题。在标准LIS中，我们处理一维数组，但这里每个元素有两个维度（宽度和高度）。嵌套条件要求两个维度都严格递增。 关键思路 ： 先对信封排序：按宽度升序，宽度相同时按高度降序。 对排序后的高度序列求LIS。 为什么这样排序？ 宽度升序确保在后续处理中，宽度条件自然满足（只需关注高度）。 宽度相同时高度降序，是为了避免相同宽度的信封被错误地嵌套（因为宽度必须严格递增，相同宽度不能嵌套）。 步骤2：排序信封 对示例 [[5,4],[6,4],[6,7],[2,3]] 排序： 按宽度升序： [2,3], [5,4], [6,7], [6,4] 宽度相同时（如两个宽度6），高度降序： [6,7] 在 [6,4] 前面。 排序后序列： [[2,3], [5,4], [6,7], [6,4]] 对应高度序列： [3, 4, 7, 4] 步骤3：在高度序列上求LIS 现在问题转化为在高度序列 [3, 4, 7, 4] 上求最长递增子序列的长度。 LIS算法（贪心 + 二分查找） ： 维护一个数组 dp ，其中 dp[i] 表示长度为 i+1 的递增子序列的最小末尾值。 遍历每个高度，用二分查找确定它在 dp 中的位置： 如果当前高度大于 dp 中所有元素，则追加到末尾。 否则，替换第一个大于等于它的元素（保持 dp 数组的单调性）。 过程演示 ： 高度 3 ： dp = [3] 高度 4 ：大于 3 ，追加 → dp = [3, 4] 高度 7 ：大于 4 ，追加 → dp = [3, 4, 7] 高度 4 ：替换第一个 >=4 的元素（ dp[1]=4 ）→ dp = [3, 4, 7] （长度不变） 最终 dp 的长度为 3 ，即最长嵌套信封数为 3 。 步骤4：算法实现细节 排序复杂度： O(n log n) LIS贪心二分复杂度： O(n log n) 总复杂度： O(n log n) 空间复杂度： O(n) 边界情况 ： 空信封列表：返回 0 所有信封宽度相同：高度降序排序后，LIS长度为 1 （因为宽度不能相同） 步骤5：为什么这样能保证宽度严格递增？ 排序后，当我们遍历高度序列时，信封是按宽度从小到大处理的。如果两个信封宽度相同，由于高度降序，后一个信封的高度不会大于前一个（避免相同宽度的信封形成递增序列）。因此，在高度序列中形成的任何递增子序列，其对应的信封宽度一定是严格递增的。 总结 通过排序将二维问题降为一维，再利用LIS的贪心二分优化，即可高效求解。这种方法确保了嵌套条件（宽度和高度都严格递增）被满足，且时间复杂度最优。