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) 贪心 + 二分代码
{
{
(envelopes == || envelopes.length == ) {
;
}
Arrays.sort(envelopes, (a, b) -> {
(a[] != b[]) {
a[] - b[];
} {
b[] - a[];
}
});
envelopes.length;
[] tails = [n];
;
([] e : envelopes) {
e[];
Arrays.binarySearch(tails, , len, h);
(idx < ) {
idx = -idx - ;
}
tails[idx] = h;
(idx == len) {
len++;
}
}
len;
}
}
