力扣动态规划——0302

最长递增子序列给定一个数组，求最长的、满足递增（或非递减）的子序列长度。朴素 DP：O (n²)贪心 + 二分O(n log n)维护一个数组tailstails[i]表示长度为 i+1 的递增子序列的最小可能末尾值。越小，后面越容易接更长的序列。LIS 贪心 + 二分是通用模板严格递增 / 非递减只在二分条件区分套娃信封 = 排序 + 严格递增 LIS障碍路线 = 非递减 LIS（每个位置求长

m0_61261153

951人浏览 · 2026-03-02 10:11:36

m0_61261153 · 2026-03-02 10:11:36 发布

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;
    }
}