leetcode-go/动态规划/87-最长递增子序列.md

---
tags: [算法/动态规划, 线性DP, 二分查找, 贪心]
create time: 2026-05-16 19:00
---

# 300. 最长递增子序列（Longest Increasing Subsequence）

> [!quote] LeetCode 原题 · 中等
> 给你一个整数数组 `nums`，找到其中 **最长严格递增子序列** 的长度。
>
> **子序列** 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
>
> - 输入范围：`1 <= nums.length <= 2500`，`-10⁴ <= nums[i] <= 10⁴`

## 题面

**示例 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
```

## 思路

### 方法一：O(n²) 动态规划

> [!question] 💡 思考
> 题目要求"子序列"（不要求连续），和"子数组"（必须连续）有什么本质区别？这种区别对 DP 的设计产生了什么影响？

子序列允许跳过元素，这意味着在考虑每个位置时，我们需要回头"查看所有可能的 preceding 状态"——而不是只看不相邻的前一个。这正是 LIS 的 DP 核心。

#### 第一步：定义状态

> `dp[i]` = 以 `nums[i]` **结尾**的最长递增子序列的长度

关键理解：这里定义的 LIS **必须以 nums[i] 作为结尾元素**。这个约束让状态具有了"最优子结构"。

#### 第二步：推导转移方程

对于位置 i，我们枚举所有 j < i：

- 如果 `nums[j] < nums[i]`，说明可以把 `nums[i]` 接到以 `nums[j]` 结尾的子序列后面，形成长度为 `dp[j] + 1` 的递增子序列
- 我们取所有合法 j 中的最大值

> **`dp[i] = max(dp[j] + 1)`**，对所有满足 `0 ≤ j < i` 且 `nums[j] < nums[i]` 的 j
>
> 若不存在这样的 j（即前面的元素都不比它小），则 `dp[i] = 1`（自身构成子序列）

```mermaid
flowchart TD
    subgraph "以 nums[5]=7 为例 (nums=[10,9,2,5,3,7,...])"
        A["dp[5]\n= max(dp[j]+1)\nfor nums[j]<7"] --> B["j=2: dp[2]=1\nnums[2]=2 < 7 → 2"]
        A --> C["j=3: dp[3]=2\nnums[3]=5 < 7 → 3"]
        A --> D["j=4: dp[4]=2\nnums[4]=3 < 7 → 3"]
        B --> E["候选值: 2"]
        C --> F["候选值: 3 ★"]
        D --> G["候选值: 3 ★"]
        F --> H["dp[5] = 3\n→ [2,5,7] 或 [2,3,7]"]
        G --> H
    end

    style A fill:#e7f3ff,stroke:#3b82f6
    style H fill:#dcfce7,stroke:#16a34a
```

#### 第三步：确定最终答案

> [!question] 💡 思考
> dp[n-1] 就是答案吗？

不一定！因为 `dp[i]` 表示"以 nums[i] 结尾"的 LIS 长度，但**全局最长递增子序列可能不以最后一个元素结尾**。所以答案是 **dp 数组中的最大值**。

```mermaid
flowchart LR
    subgraph "填表完成后扫描最大值"
        A["dp[0]=1"] --> B["dp[1]=1"]
        B --> C["dp[2]=1"]
        C --> D["dp[3]=2"]
        D --> E["dp[4]=2"]
        E --> F["dp[5]=3"]
        F --> G["dp[6]=4 ★★★"]
        G --> H["dp[7]=4"]
    end

    style A fill:#fef3c7,stroke:#f59e0b
    style F fill:#fef3c7,stroke:#f59e0b
    style G fill:#dcfce7,stroke:#16a34a
    style H fill:#fef3c7,stroke:#f59e0b
```

#### 第四步：自底向上填表演示

以 `nums = [10, 9, 2, 5, 3, 7, 101, 18]` 为例：

| i | nums[i] | dp[i] 计算过程 | dp[i] |
|---|---------|--------------|-------|
| 0 | 10 | 无前驱 | **1** → [10] |
| 1 | 9 | 无前驱（10 > 9） | **1** → [9] |
| 2 | 2 | 无前驱 | **1** → [2] |
| 3 | 5 | nums[2]=2<5 → dp[2]+1 | **2** → [2,5] |
| 4 | 3 | nums[2]=2<3 → dp[2]+1 | **2** → [2,3] |
| 5 | 7 | nums[3]=5<7→3, nums[4]=3<7→3 | **3** → [2,5,7] 或 [2,3,7] |
| 6 | 101 | dp[5]=3 → 4 | **4** → [2,5,7,101] |
| 7 | 18 | dp[5]=3 → 4 | **4** → [2,5,7,18] |

答案 = max(dp) = **4** ✅

> [!summary] 💡 代码结构拆解
> - **外层 for i=1..n-1**：逐个计算每个位置结尾的 LIS 长度
> - **内层 for j=0..i-1**：回溯检查所有前驱，找最优的那条"接力链"
> - **最终 scan**：dp 数组中取最大值，因为全局最优解不一定停在末尾

### 方法二：O(n log n) 二分查找 + 贪心

> [!abstract] 🔍 核心直觉升级
> 上面 DP 的思路是"以某个元素结尾"，而 O(n log n) 方法的思路完全不同——它不再关心"以谁结尾"，而是关注"**长度为 k 的递增子序列，最小的末尾元素是什么**"。

想象你在打扑克牌——"接龙游戏"（Patience Sorting）：从左到右依次处理每张牌，把它放在最左边的、顶部数字 ≥ 它的牌堆上；如果没有这样的牌堆，就新开一堆。**最终牌堆的数量就是 LIS 的长度**。

用程序语言描述，我们维护一个数组 `tails`：

> **`tails[k]` = 长度为 `k+1` 的所有递增子序列中，末尾元素的最小值**

为什么这个数组能优化？因为它有至关重要的单调性：

> [!tip] 🧠 关键引理：tails 严格递增
> 假设长度为 k 的递增子序列最小末尾是 a，长度为 k+1 的是 b。由于任何长度为 k+1 的子序列都包含一个长度为 k 的前缀，该前缀的末尾一定小于 b，所以 a < b。
>
> 结论：**tails 严格递增** → 可以用二分查找！

#### 操作规则

对每个 `nums[i]`：

1. 在 `tails` 中**二分查找第一个 ≥ nums[i] 的位置**
   - 找到了：把这个位置的元素**替换**成 nums[i]（说明存在一个同样长度的子序列，但末尾更小了——贪心选择更有潜力）
   - 没找到（nums[i] 比所有 tails 都大）：把 nums[i]**追加**到尾部，LIS 长度 +1

```mermaid
flowchart TD
    subgraph "核心操作逻辑"
        A["nums[i]"] --> B{"二分查 tails\n首个 ≥ nums[i]?"}
        B -- "找到了" --> C["替换该位置\n→ 更小末尾, 同长度"]
        B -- "没找到" --> D["追加到尾部\n→ 延长 LIS"]
        C --> E["tails 仍严格递增 ✓"]
        D --> E
    end

    style A fill:#e7f3ff,stroke:#3b82f6
    style C fill:#fef3c7,stroke:#f59e0b
    style D fill:#dcfce7,stroke:#16a34a
    style E fill:#d1fae5,stroke:#10b981
```

#### 完整走一遍

以 `nums = [10, 9, 2, 5, 3, 7, 101, 18]` 为例：

| 步骤 | nums[i] | tails 变化 | 说明 |
|------|---------|-----------|------|
| 初始 | — | `[]` | 空 |
| 1 | 10 | `[10]` | 空，直接追加 |
| 2 | 9 | `[9]` | 9 < 10，替换 tails[0] |
| 3 | 2 | `[2]` | 2 < 9，替换 tails[0] |
| 4 | 5 | `[2, 5]` | 5 > 2，追加 |
| 5 | 3 | `[2, 3]` | 3 < 5，替换 tails[1] |
| 6 | 7 | `[2, 3, 7]` | 7 > 3，追加 |
| 7 | 101 | `[2, 3, 7, 101]` | 101 > 7，追加 → LIS 长度=4 |
| 8 | 18 | `[2, 3, 7, 18]` | 18 < 101，替换 tails[3] |

**最终 tails 长度 = 4**，即为答案 ✅

```mermaid
flowchart LR
    subgraph "tails 演变全过程"
        A["[]"] --> B["[10]"]
        B --> C["[9]"]
        C --> D["[2]"]
        D --> E["[2,5]"]
        E --> F["[2,3]"]
        F --> G["[2,3,7]"]
        G --> H["[2,3,7,101]\n★答案=4"]
        H --> I["[2,3,7,18]"]
    end

    style A fill:#f3f4f6,stroke:#6b7280
    style G fill:#fef3c7,stroke:#f59e0b
    style H fill:#dcfce7,stroke:#16a34a
    style I fill:#dbeafe,stroke:#3b82f6
```

> [!warning] ⚠️ 重要澄清：tails ≠ 实际的 LIS
> `tails` 记录的是"各长度下最小末尾"的信息，它本身不一定是一个真实的子序列。但它的**长度**恰好等于 LIS 的真实长度。上面的例子中，tail 经历了 [2,3,7,101] → [2,3,7,18]，真实 LIS 可能是 [2,5,7,101] 或 [2,3,7,18]。虽然内容不完全一致，但**长度恒等**。

## 代码提示

在动手写代码之前，想一想这些关键决策点：

> [!question] 💡 思考 1
> Go 标准库中有二分查找函数——你会选哪一个？需要注意什么？

Go 的 `sort.SearchInts` 返回目标值在有序切片中的插入位置（索引）。如果该索引等于切片长度，说明目标值比所有元素都大——正好对应"追加"的情况。如果索引 < len(tails)，说明找到了第一个 ≥ 值的元素——对应"替换"。

> [!question] 💡 思考 2
> 两种方法的空间复杂度分别是多少？有没有办法进一步降低空间？

方法一需要 dp 数组 → O(n)；方法二只需要 tails 数组 → O(n)。两者都是 O(n) 空间。不过对于方法一，如果你只需要长度而非具体序列，可以注意到 dp 数组的某些冗余信息其实不需要全部保留——但这涉及更复杂的技巧，面试中答出标准的 O(n) 即可。

## 技巧

### 变体速查：边界微调决定不同语义

> [!tip] ⚡ 小技巧：非严格递增 / 最长递减子序列
>
> | 变体 | 改动点 |
> |------|--------|
> | 非严格递增（允许相等） | 方法一中 `nums[j] < nums[i]` 改为 `≤`；方法二中二分改为"第一个 > nums[i]" |
> | 最长递减子序列 | 反转数组后求 LIS，或在比较时反过来：`>` 变 `<` |
> | 求最长非递减子序列 | 使用 `sort.Search` 自定义比较函数，找第一个 **大于** 而不是 **大于等于** |

### 构造实际子序列

> [!abstract] 🔍 进阶：不只是长度
>
> 如果需要**输出具体的 LIS**，方法一更容易扩展：维护一个 `parent[i]` 数组记录每个 dp[i] 对应的上一个元素下标，最后从 dp 最大处回溯即可。方法二较难还原（可以用额外数据结构实现但不常见）。

#### 方法一：DP + parent 数组回溯（推荐 ✅）

核心思想：**在转移时同时记录"父节点"**——就像链表一样，从终点一步步往回走就能拼出整条链。

```go
// lengthOfLISWithSequence returns both the length and the actual LIS.
func lengthOfLISWithSequence(nums []int) (int, []int) {
	n := len(nums)
	if n == 0 {
		return 0, nil
	}

	dp := make([]int, n)    // dp[i] = 以 nums[i] 结尾的 LIS 长度
	parent := make([]int, n) // parent[i] = dp[i] 对应的前驱下标，-1 表示无前驱
	for i := range dp {
		dp[i] = 1
		parent[i] = -1
	}

	// 自底向上填表
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] && dp[j]+1 > dp[i] {
				dp[i] = dp[j] + 1
				parent[i] = j // ★ 关键：记录父节点
			}
		}
	}

	// 找到 dp 最大值及其索引
	maxIdx := 0
	for i := 1; i < n; i++ {
		if dp[i] > dp[maxIdx] {
			maxIdx = i
		}
	}

	// ★ 从 maxIdx 沿 parent 链回溯，逆序拼出 LIS
	result := make([]int, 0, dp[maxIdx])
	for cur := maxIdx; cur != -1; cur = parent[cur] {
		result = append(result, nums[cur])
	}

	// 此时 result 是逆序的（从后往前），需要反转
	for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
		result[i], result[j] = result[j], result[i]
	}

	return dp[maxIdx], result
}
```

**走一遍演示**（`nums = [10,9,2,5,3,7,101,18]`）：

| i | nums[i] | dp[i] | parent[i] | 说明 |
|---|---------|-------|-----------|------|
| 0 | 10 | 1 | -1 | 单独起点 |
| 1 | 9 | 1 | -1 | 无前驱 |
| 2 | 2 | 1 | -1 | 无前驱 |
| 3 | 5 | 2 | 2 | 接在 nums[2]=2 后面 |
| 4 | 3 | 2 | 2 | 接在 nums[2]=2 后面 |
| 5 | 7 | 3 | 3 | 接在 nums[3]=5 后面（dp[3]+1=3 > dp[4]+1=3 不更优，取先更新的） |
| 6 | 101 | 4 | 5 | 接在 nums[5]=7 后面 |
| 7 | 18 | 4 | 5 | 同样长度为 4，接在 nums[5]=7 后面 |

**回溯过程**：`maxIdx = 6`（dp[6]=4 是第一个出现的最大值）

```
第1步: cur=6,  nums[6]=101 → result=[101]      parent[6]=5
第2步: cur=5,  nums[5]=7   → result=[101,7]     parent[5]=3
第3步: cur=3,  nums[3]=5   → result=[101,7,5]   parent[3]=2
第4步: cur=2,  nums[2]=2   → result=[101,7,5,2] parent[2]=-1 → 停止

反转后: [2,5,7,101] ✅
```

> [!tip] ⚡ 设计要点
> - **为什么要等全部填完再回溯？** 因为只有在所有状态都计算完后，才能确定全局最优解的终点在哪
> - **如果有多个相同长度的 LIS 怎么办？** 上面的实现返回的是最先达到的那个。如果只需要任意一个，这就够了；如果需要全部枚举，则需要在遍历结束时收集所有 `dp[i]==maxLen` 的 i 分别回溯
> - **空间代价**：多了 O(n) 的 `parent` 数组，整体仍然是 O(n²) 时间、O(n) 空间

> [!warning] ⚠️ 为什么不推荐方法二还原？
> `tails` 数组中的值会被反复替换，它只是各长度的"最优末尾候选"，不是真实路径。虽然可以通过额外维护一棵前驱树来还原，但实现复杂且容易出错，面试中很少要求。用方法一的 parent 数组回溯才是标准做法。

### 何时选哪种方法？

> [!question] 💡 面试官追问：为什么要用 O(n log n) 而不是 O(n²)？

关键指标看 n 的范围：

| 约束 | 推荐方法 | 理由 |
|------|----------|------|
| n ≤ 3000 | O(n²) DP | 约 9×10⁶ 次操作，足够快且代码简单 |
| n ≤ 10⁵ | O(n log n) 二分 | 约 1.7×10⁶ 次操作，差距明显 |
| n ≤ 10⁶+ | 必须 O(n log n) | O(n²) 超时 |

本题 n ≤ 2500，两种都能 AC，但 **O(n log n) 是这道题的灵魂考点**，面试务必掌握。

| 方法 | 时间 | 空间 | 评价 |
|------|------|------|------|
| DP 填表 | O(n²) | O(n) | 直观易懂，容易扩展构造序列 |
| 二分 + 贪心（推荐 ✅） | O(n log n) | O(n) | 高效优雅，面试加分项 |

## 代码

### Go 语言实现

#### 版本一：O(n²) 动态规划

```go
// lengthOfLIS returns the length of the longest strictly increasing subsequence.
func lengthOfLIS(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}

	// dp[i] = 以 nums[i] 结尾的最长递增子序列的长度
	// 初始化全为 1，因为每个元素自身就是一个长度为 1 的子序列
	dp := make([]int, n)
	for i := range dp {
		dp[i] = 1
	}

	// 自底向上填表：对每个位置 i，遍历所有前驱 j < i
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] { // 满足递增条件
				if dp[j]+1 > dp[i] {
					dp[i] = dp[j] + 1
				}
			}
		}
	}

	// 答案是 dp 数组中的最大值
	result := 0
	for _, v := range dp {
		if v > result {
			result = v
		}
	}
	return result
}
```

> [!summary] 💡 代码说明
> - **初始化**：所有 dp[i] = 1（每个元素单独构成子序列）
> - **外层 i**：从左往右，逐个"放置"当前元素
> - **内层 j**：回头看所有前驱，找到能把当前元素接上去的"最佳父节点"
> - **最后扫描**：最大值即全局 LIS 长度

#### 版本二：O(n log n) 二分 + 贪心（推荐 ✅）

```go
// lengthOfLIS returns the length of the longest strictly increasing subsequence.
// Time complexity: O(n log n), Space complexity: O(n).
func lengthOfLIS(nums []int) int {
	// tails[i] = 长度为 i+1 的所有递增子序列中，最小的末尾元素
	var tails []int

	for _, num := range nums {
		// 二分查找 tails 中第一个 >= num 的位置
		pos := sort.SearchInts(tails, num)

		if pos < len(tails) {
			tails[pos] = num // 替换：让同样长度的子序列末尾更小
		} else {
			tails = append(tails, num) // 追加：发现更长的递增子序列
		}
	}

	return len(tails)
}
```

> [!summary] 💡 代码结构拆解
> - **sort.SearchInts**：Go 标准库的二分搜索，返回目标值在有序切片中的插入位置（保证左侧元素 < 目标，右侧元素 ≥ 目标）
> - **pos < len(tails)**：找到可替换位置 → 贪心地让末尾更小，增加未来扩展的可能性
> - **pos == len(tails)**：所有 tails 元素都 < num → num 能延长 LIS，长度 +1
> - **核心循环仅 5 行**，简洁优雅

### 执行过程演示（nums = [10,9,2,5,3,7,101,18]）

```
tails = []

num=10: SearchInts([], 10) → 0 (len=0, 追加)
tails = [10]

num=9:  SearchInts([10], 9) → 0 (tails[0]=10 >= 9, 替换)
tails = [9]

num=2:  SearchInts([9], 2) → 0 (tails[0]=9 >= 2, 替换)
tails = [2]

num=5:  SearchInts([2], 5) → 1 (1 == len, 追加)
tails = [2, 5]

num=3:  SearchInts([2,5], 3) → 1 (tails[1]=5 >= 3, 替换)
tails = [2, 3]

num=7:  SearchInts([2,3], 7) → 2 (2 == len, 追加)
tails = [2, 3, 7]

num=101: SearchInts([2,3,7], 101) → 3 (3 == len, 追加)
tails = [2, 3, 7, 101] ← LIS 长度达到 4

num=18: SearchInts([2,3,7,101], 18) → 3 (tails[3]=101 >= 18, 替换)
tails = [2, 3, 7, 18]

结果: len(tails) = 4 ✅
```

### 复杂度分析

| 维度 | 方法一（DP） | 方法二（二分） |
|------|-------------|---------------|
| **时间** | O(n²) — 两层嵌套循环，每次常数操作 | O(n log n) — n 次迭代，每次二分 O(log L)，L ≤ n |
| **空间** | O(n) — dp 数组 | O(n) — tails 数组 |

代入本题约束 n ≤ 2500：
- 方法一：~6.25 × 10⁶ 次操作，轻松通过
- 方法二：~2500 × 12 ≈ 3 × 10⁴ 次操作，几乎瞬时完成

## 举一反三

这道题是 **线性 DP 与贪心 + 二分** 结合的经典范例，也是 LeetCode 中"模式识别"价值极高的一题：

- [[86-单词拆分]] — 同样是逐状态递推，但这里的"选择分支"是从所有前驱中选择
- [[84-完全平方数]] — 与 LIS 的 DP 写法内核相似（枚举起跳点取极值），但目标函数从"求最大长度"变成了"求最小个数"
- LeetCode 673. 最长递增子序列的个数 —— **变种**：在 DP 基础上多维护一个 count 数组，统计每个位置结尾的方案数
- LeetCode 354. 俄罗斯套娃信封问题 —— **二维 LIS 模板题**：先按一维排序，再对另一维求 LIS
- LeetCode 392. 判断子序列 —— **简化版**：只需判断是否存在（返回 true/false 而非长度），双指针即可
- LeetCode 674. 最长连续递增序列 —— **降维权**：子序列变成连续子数组，直接一次扫描即可

> [!summary] 📌 本节要点
> 1. **方法一（DP）**：定义 dp[i] = 以 nums[i] 结尾的 LIS 长度，转移 dp[i] = max(dp[j]+1)，总时间 O(n²)
> 2. **方法二（二分+贪心）**：维护 tails 数组——长度为 k+1 的递增子序列的最小末尾，利用单调性做二分，总时间 O(n log n)
> 3. tails 严格递增是关键引理，保证了二分查找的正确性
> 4. tails 本身不一定是真实 LIS，但其长度一定等于 LIS 长度
> 5. 面试中优先展示方法二，同时能够解释方法一