1. 前置知识：什么是 LIS？
LIS = Longest Increasing Subsequence（最长递增子序列）
给定一个数组，求最长的、满足递增（或非递减）的子序列长度。
- 朴素 DP：O(n^2)，
dp[i] = max(dp[j] + 1)，j < i && nums[j] < nums[i] - 优化解法：贪心 + 二分 O(n log n)
贪心思想：维护一个数组 tails，tails[i] 表示长度为 i+1 的递增子序列的最小可能末尾值。越小，后面越容易接更长的序列。
2. 题目一：俄罗斯套娃信封（严格递增 LIS）
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）
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. 两道题核心对比（一张表看懂）
| 题目 | 序列类型 | 二分查找目标 |
|---|---|---|
| 套娃信封 | 严格递增 | 第一个 >= x |
| 障碍赛跑 | 非递减 | 第一个 > x |
共同点：
- 都是 LIS 模型
- 都用贪心 + 二分优化到 O(n log n)
- 都维护'最小末尾'数组
不同点：
- 套娃信封需要先排序
- 障碍路线直接求 LIS
- 二分条件差一个等号
5. 文末总结
看完这两道题，你应该彻底掌握：
- LIS 贪心 + 二分是通用模板
- 严格递增 / 非递减 只在二分条件区分
- 套娃信封 = 排序 + 严格递增 LIS
- 障碍路线 = 非递减 LIS（每个位置求长度）
- O(n log n) 是大数据量下的唯一解法
