线性动态规划：俄罗斯套娃信封问题 题目描述 给定一个二维整数数组 envelopes ，其中 envelopes[i] = [w_i, h_i] 表示第 i 个信封的宽度和高度。当一个信封的宽度和高度都大于另一个信封时，它可以套进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封组成一组“俄罗斯套娃”信封（即一个信封套在另一个信封里）。注意：信封不能旋转。 示例 输入： envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出： 3 解释：最多信封的套娃序列是 [2,3] → [5,4] → [6,7] ，长度为 3。 解题过程 步骤 1：问题分析 此问题本质是寻找一个序列，其中每个信封的宽度和高度都严格递增。这与“最长递增子序列（LIS）”问题类似，但需同时满足两个维度的递增条件。直接暴力枚举所有信封排列会超时，需采用动态规划优化。 步骤 2：排序预处理 为了将二维问题转化为一维 LIS 问题，我们先对信封排序： 按宽度 w 升序 排序。 若宽度相同，按高度 h 降序 排序（目的是避免宽度相同的信封被错误地套在一起，因为题目要求严格递增）。 示例排序后： [[2,3], [5,4], [6,7], [6,4]] → 宽度相同（如 [6,7] 和 [6,4] ）时，高度降序可保证在后续 LIS 中只可能取其中一个。 步骤 3：问题转化 排序后，问题转化为在高度数组 h 中寻找最长严格递增子序列。例如高度数组为 [3,4,7,4] ，其 LIS 为 [3,4,7] ，对应信封序列 [2,3] → [5,4] → [6,7] 。 步骤 4：动态规划求解 LIS 定义 dp[i] 表示以第 i 个信封为结尾的最长递增子序列长度。 转移方程： dp[i] = max(dp[j]) + 1 ，其中 j < i 且 h[j] < h[i] 最终答案为 max(dp[i]) 。 时间复杂度：O(n²)，适用于较小规模数据。 步骤 5：优化至 O(n log n) 对于较大规模数据，采用贪心 + 二分查找优化 LIS 求解： 维护一个数组 tail ， tail[k] 表示长度为 k+1 的递增子序列的最小末尾值。 遍历每个高度 h ： 若 h 大于 tail 的最后一个元素，直接追加到末尾。 否则，用二分查找找到第一个大于等于 h 的位置，将其替换为 h （保证后续序列更易扩展）。 最终 tail 的长度即为最长递增子序列长度。 示例高度数组 [3,4,7,4] 的优化过程： h=3 → tail = [3] h=4 → 4>3 → tail = [3,4] h=7 → 7>4 → tail = [3,4,7] h=4 → 替换 tail[1]=4 → tail = [3,4,7] （长度不变） 最终长度 3。 总结 通过排序将二维问题转化为一维 LIS，再通过动态规划或贪心优化求解。关键点在于排序时对相同宽度的信封按高度降序处理，避免同一宽度的信封被重复选取。