300. 最长递增子序列

题目链接（中等）

题目描述

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

数据范围：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

进阶：你能将算法的时间复杂度降低到 O(n log(n)) 吗？

示例

示例 1：

输入： nums = [10,9,2,5,3,7,101,18]
输出： 4
解释： 最长递增子序列是 [2,3,7,101]，因此长度为 4。

示例 2：

输入： nums = [0,1,0,3,2,3]
输出： 4

示例 3：

输入： nums = [7,7,7,7,7,7,7]
输出： 1

核心思路

子序列不要求连续，只要求保持原数组顺序。严格递增意味着不能有相等元素。

两种主流解法：

1. 动态规划：dp[i] 表示以 nums[i] 结尾的 LIS 长度，时间 $O(n^2)$；
2. 贪心 + 二分：维护一个「长度为 i 的 LIS 的最小末尾元素」数组 d，时间 $O(n \log n)$，满足进阶要求。

---

方法一：动态规划

思路及解法

定义 dp[i] 为「以 nums[i] 结尾的最长严格递增子序列的长度」。

转移思路：对于每个 i，枚举所有 j < i：

• 如果 nums[j] < nums[i]，说明可以把 nums[i] 接到以 nums[j] 结尾的 LIS 后面；
• 此时 dp[i] 可以取 dp[j] + 1。

转移方程：

$$dp[i] = \max_{0 \le j < i,\ nums[j] < nums[i]} dp[j] + 1$$

边界：每个元素至少可以单独构成长度为 1 的子序列，所以 dp[i] 初始为 1。

答案：max(dp)，因为 LIS 不一定以最后一个元素结尾。

直觉理解：以 nums[i] 结尾的 LIS，要么从前面某个比它小的数「接」过来，要么只包含它自己。

代码

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

复杂度分析

• 时间复杂度：$O(n^2)$，共 $n$ 个状态，每个状态枚举 $O(n)$ 个前置状态。
• 空间复杂度：$O(n)$，dp 数组长度为 $n$。

---

方法二：贪心 + 二分查找

思路及解法

贪心思想：要让递增子序列尽可能长，就要让序列增长得尽可能慢，也就是让「末尾元素」尽可能小。

维护数组 d：d[i] 表示「长度为 i + 1 的最长递增子序列的最小末尾元素」。

关键性质：d 数组是严格递增的。

为什么 d 严格递增？

反证：假设存在 j < i 使得 d[j] >= d[i]。考虑长度为 i + 1 的 LIS，它的末尾是 d[i]。删掉最后 i - j 个元素，得到一个长度为 j + 1 的子序列，其末尾元素 < d[i] <= d[j]。这与 d[j] 是长度为 j + 1 的 LIS 的最小末尾元素矛盾。

遍历流程：对每个 x = nums[i]：

1. 若 d 为空或 x > d[-1]：说明可以延长，直接 append，LIS 长度 +1；
2. 否则，在 d 中二分查找第一个 >= x 的位置 loc，把 d[loc] 更新为 x。

为什么用「替换」而不是「插入」？

因为替换不会改变 LIS 的长度，但会让「末尾元素更小」，为后续增长留出更多空间。这是贪心的关键。

最终答案：len(d)。

举例：nums = [0,8,4,12,2]

步骤	x	d 数组	说明
1	0	[0]	初始
2	8	[0, 8]	8 > 0，延长
3	4	[0, 4]	4 > 0 但 < 8，替换 8
4	12	[0, 4, 12]	12 > 4，延长
5	2	[0, 2, 12]	2 > 0 但 < 4，替换 4

最终 len(d) = 3，答案正确。

注意：d 数组不是 LIS 本身，只是「每个长度对应的最小末尾」。所以本题只能求长度，不能还原 LIS 的具体元素。

代码

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        d = []
        for x in nums:
            if not d or x > d[-1]:
                d.append(x)
            else:
                # 找到第一个 >= x 的位置，替换为 x
                idx = bisect_left(d, x)
                d[idx] = x
        return len(d)

也可以用 bisect_right(d, x)，因为 d 严格递增，遇到相等元素时 bisect_left 和 bisect_right 结果相同。用哪个都行。

手写二分版（面试时如果不能调库）：

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        d = []
        for x in nums:
            if not d or x > d[-1]:
                d.append(x)
            else:
                l, r = 0, len(d) - 1
                loc = r
                while l <= r:
                    mid = (l + r) // 2
                    if d[mid] >= x:
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                d[loc] = x
        return len(d)

复杂度分析

• 时间复杂度：$O(n \log n)$，每个元素二分一次。
• 空间复杂度：$O(n)$，d 数组最长为 n。

---

两种方法对比

方法	时间	空间	是否满足进阶	特点
动态规划	$O(n^2)$	$O(n)$	❌	思路直观，容易讲清
贪心 + 二分	$O(n \log n)$	$O(n)$	✅	效率最优，但 d 含义需要理解

推荐：

• 面试开场：先讲 DP，因为它的状态定义更自然；
• 追问优化：再讲 贪心 + 二分，满足进阶要求；
• 写代码：如果能调库，直接用 bisect_left，代码最短。

---

关键细节

1. 为什么是「严格递增」

题目要求严格递增，所以判断是 nums[j] < nums[i]（不是 ≤），二分也是找第一个 ≥ x 的位置替换。

如果题目改成「非递减」（允许相等），二分应该换成 bisect_right。

2. d 数组的实际含义

d[i] = 「长度为 i + 1 的 LIS 的最小末尾元素」。

记住：d 不是 LIS 本身。 例如 nums = [0,8,4]，d = [0, 4]，但 LIS 是 [0, 8]。

3. 为什么 d 是严格递增的

反证法：若 d[j] >= d[i]（j < i），可以构造出一个更短的 LIS 且末尾更小，矛盾。

这保证了二分查找的可行性。

4. 为什么直接返回 len(d) 就是答案

d 的长度就是当前找到的最长递增子序列的长度。每次替换或 append 都在维护这个长度的最小末尾，不会影响长度，只会让后续更容易延长。

5. 与 LC 674（最长连续递增序列）的区别

• LC 300：子序列，元素可以不连续，求最长；
• LC 674：子数组，元素必须连续，求最长。

两者状态定义不同，不要混淆。

---

总结

• DP 方法：
  • dp[i] = 以 nums[i] 结尾的 LIS 长度；
  • 转移：dp[i] = max(dp[j] + 1)，j < i 且 nums[j] < nums[i]；
  • 答案：max(dp)；
  • 时间 $O(n^2)$、空间 $O(n)$；
• 贪心 + 二分：
  • 维护 d[i] = 长度为 i+1 的 LIS 的最小末尾；
  • 遇到 x > d[-1] 就 append，否则二分找第一个 >= x 的位置替换；
  • 答案：len(d)；
  • 时间 $O(n \log n)$、空间 $O(n)$；
• 通用套路：「最长递增子序列」+ 「元素可不连续」→ 优先考虑贪心 + 二分。

相关题目

• LC 674. 最长连续递增序列（子数组，必须连续）
• LC 354. 俄罗斯套娃信封问题（二维 LIS，先排序再套 LIS）
• LC 1143. 最长公共子序列（二维 DP）
• LC 673. 最长递增子序列的个数（LIS + 计数）

应用 1 - 不相交的线段

首先，如果两个线段 $(l_1, r_1)$ 和 $(l_2, r_2)$ 相交（假设 $l_1 < l_2$），我们可以注意到 $l_1 < l_2 \implies r_1 > r_2$。

这意味着一组不相交的线段对于所有对 $(i, j)$ 都满足 $l_i < l_j \implies r_i < r_j$！

设 $A$ 是一个数组，其中 $A[i] = x$ 表示位于位置 $i$ 的右端点的线段的左端点位于位置 $x$。

如果我们被要求找出不相交线段集的最大大小，答案将是 $A$ 的最长递增子序列！

---

应用 2 - 最少递增子序列数

引理（简单）: 覆盖 $A$ 所需的最少递增子序列数至少等于 $A$ 最长非递增子序列的长度。

命题: 覆盖 $A$ 所需的最少递增子序列的数量等于 $A$ 最长非递增子序列的长度！

证明: 设 $f_i$ 表示以 $A_i$ 结尾的最长非递增子序列的长度。那么对于固定的 $t$，满足 $f_i = t$ 的 $A_i$ 对于每个 $t$ 都是一个递增子序列。所以我们用（最长非递增子序列的长度）个递增子序列覆盖了 $A$。

另一种证明: 这只是 Dilworth 定理的一个特例。

---

示例 - PCB

Focus Problem: 在继续之前，请尽力解决这个问题！

这个问题要求我们找到最小数量的不交线段集。

from bisect import bisect_left

n = int(input())
board = []
endpoints = []
for _ in range(n):
    l, r = map(int, input().split())
    board.append((l, r))
board.sort()

endpoints.append(board[0][1])
for x in range(1, n):
    v = board[x][1]
    if v < endpoints[-1]:
        endpoints.append(v)
    else:
        index = bisect_left(
            [-x for x in endpoints], -v
        )  # invert list in order to use bisect_left
        endpoints[index] = v
print(len(endpoints))

---

总结

解法	时间复杂度	空间复杂度
暴力 DP	$O(N^2)$	$O(N)$
二分查找优化	$O(N \log N)$	$O(N)$
RMQ/线段树	$O(N \log N)$	$O(N)$

---

经典问题

题目	难度	描述
Increasing Subsequence	Easy	计算最长递增子序列长度
PCB	Hard	不相交线段集问题