力扣动态规划——0302

1. 前置知识：什么是 LIS？

LIS = Longest Increasing Subsequence最长递增子序列

给定一个数组，求最长的、满足递增（或非递减）的子序列长度。

• 朴素 DP：O (n²)dp[i] = max(dp[j] + 1)，j < i && nums[j] < nums[i]
• 优化解法：贪心 + 二分 O(n log n)

贪心思想：维护一个数组 tails，tails[i] 表示长度为 i+1 的递增子序列的最小可能末尾值。越小，后面越容易接更长的序列。

2. 题目一：俄罗斯套娃信封（严格递增 LIS）

LeetCode 354. Russian Doll Envelopes

2.1 题目描述

给定若干个信封，每个信封以 [w, h] 表示宽度和高度。当且仅当信封 A 的宽度和高度 都严格大于 信封 B 时，B 可以套入 A。求最多能套多少层。

2.2 关键思路：二维 → 一维 LIS

我们希望：

• 宽度已经有序，只需要判断高度
• 高度满足严格递增 → 就是 LIS 长度

2.3 排序规则（非常重要）

Arrays.sort(envelopes, (a, b) -> { if (a[0] != b[0]) { return a[0] - b[0]; // 宽度升序 } else { return b[1] - a[1]; // 宽度相同，高度降序 } }); 

2.4 为什么宽度相同要高度降序？

因为：宽度相同不能嵌套！

如果宽度相同、高度升序：[3,4], [3,5]高度 4 < 5，LIS 会认为可以递增，结果错误。

降序排列：[3,5], [3,4]5 > 4，不会被算进递增序列，保证正确性。

2.5 O (n log n) 贪心 + 二分代码

class Solution { public int maxEnvelopes(int[][] envelopes) { if (envelopes == null || envelopes.length == 0) { return 0; } Arrays.sort(envelopes, (a, b) -> { if (a[0] != b[0]) { return a[0] - b[0]; } else { return b[1] - a[1]; } }); int n = envelopes.length; int[] tails = new int[n]; int len = 0; for (int[] e : envelopes) { int h = e[1]; int idx = Arrays.binarySearch(tails, 0, len, h); if (idx < 0) { idx = -idx - 1; } tails[idx] = h; if (idx == len) { len++; } } return len; } } 

2.6 二分查找解释

• 查找第一个 >= 当前高度 的位置
• 替换它，让末尾尽可能小
• 如果比所有都大，直接加入，长度 + 1

3. 题目二：最长障碍赛跑路线（非递减 LIS）

LeetCode 964. Longest Obstacle Course At Each Position

3.1 题目描述

给一个数组 obstacles，表示障碍高度。对每个位置 i，求：

• 必须包含第 i 个障碍
• 顺序不变
• 高度 非递减（可以相等）的最长子序列长度。

3.2 关键点

这是 非递减 LIS，不是严格递增！允许：<=

3.3 与套娃信封的区别

• 套娃信封：严格递增 → 找第一个 >= x
• 障碍路线：非递减 → 找第一个 > x

只改一行二分条件！

3.4 完整代码

class Solution { public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { List<Integer> list = new ArrayList<>(); int n = obstacles.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { int x = obstacles[i]; int l = 0, r = list.size(); while (l < r) { int mid = (l + r) / 2; if (list.get(mid) <= x) { l = mid + 1; } else { r = mid; } } if (l == list.size()) { list.add(x); } else { list.set(l, x); } ans[i] = l + 1; } return ans; } } 

3.5 为什么这么写二分？

我们要找：第一个大于 x 的位置 l

那么：

• 0 ~ l-1 都是 ≤x
• 所以以 x 结尾的最长长度 = l + 1

完美对应题目要求的非递减。

4. 两道题核心对比（一张表看懂）

共同点：

• 都是 LIS 模型
• 都用贪心 + 二分优化到 O (n log n)
• 都维护 “最小末尾” 数组

不同点：

• 套娃信封需要先排序
• 障碍路线直接求 LIS
• 二分条件差一个等号

5. 文末总结

看完这两道题，你应该彻底掌握：

1. LIS 贪心 + 二分是通用模板
2. 严格递增 / 非递减 只在二分条件区分
3. 套娃信封 = 排序 + 严格递增 LIS
4. 障碍路线 = 非递减 LIS（每个位置求长度）
5. O (n log n) 是大数据量下的唯一解法