281 lines
11 KiB
Markdown
281 lines
11 KiB
Markdown
---
|
||
tags: ["LeetCode", "贪心算法", "数组", "中等"]
|
||
create time: 2026-05-16 14:30
|
||
---
|
||
|
||
# 78-跳跃游戏
|
||
|
||
## 题面
|
||
|
||
给定一个非负整数数组 `nums`，你最初位于数组的**第一个下标**。数组中的每个元素代表你在该位置可以跳跃的最大长度。
|
||
|
||
判断你是否能够到达最后一个下标，如果可以，返回 `true`；否则，返回 `false`。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：nums = [2,3,1,1,4]
|
||
输出：true
|
||
解释：可以先跳 1 步，从下标 0 到达下标 1，然后再从下标 1 跳 3 步到达最后一个下标。
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：nums = [3,2,1,0,4]
|
||
输出：false
|
||
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0，所以永远不可能到达最后一个下标。
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- `1 <= nums.length <= 10⁴`
|
||
- `0 <= nums[i] <= 10⁵`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
> 从一个位置跳到另一个位置，本质上是在做"可达范围"的扩张。想象你是一个探险家站在起点，每一步可以选择向前走的距离——关键不在于你选择走几步，而在于你能覆盖的**最远边界**能否不断向右推进，直到触及终点。
|
||
|
||
### 方法一：记忆化搜索 / DFS ❌
|
||
|
||
直觉上，可以从当前位置尝试所有可能的跳跃距离（1 到 nums[i]），递归判断是否有任意一条路径能到达终点：
|
||
|
||
```
|
||
canJump(pos):
|
||
if pos >= n-1: return true
|
||
for step from 1 to nums[pos]:
|
||
if canJump(pos + step): return true
|
||
return false
|
||
```
|
||
|
||
配合记忆化避免重复计算，但状态数是 O(n²)，在最坏情况下（如全为较大值）仍然超时。
|
||
|
||
- **时间复杂度：O(n²)** — 每个位置可能触发多个子问题
|
||
- **空间复杂度：O(n)** — 递归栈 + 记忆化数组
|
||
|
||
当 n ≤ 10⁴ 且 nums[i] 较大时，这个方法不够高效。有没有办法一次扫完就出结果？
|
||
|
||
### 方法二：动态规划 ❌
|
||
|
||
定义布尔数组 `dp[i]` 表示下标 `i` 是否可达。初始化 `dp[0] = true`，然后从左到右枚举每个可达的位置 `j`，将其能到达的所有位置标记为可达：
|
||
|
||
```
|
||
dp[0] = true
|
||
for j from 0 to n-1:
|
||
if dp[j]:
|
||
for k from 1 to nums[j]:
|
||
if j + k < n:
|
||
dp[j + k] = true
|
||
return dp[n-1]
|
||
```
|
||
|
||
以 `nums = [2,3,1,1,4]` 为例：
|
||
|
||
| j | dp[j] | nums[j] | 被标记为 true 的位置 | dp 数组状态 |
|
||
|---|-------|---------|-------------------|------------|
|
||
| 0 | ✅ | 2 | 1, 2 | `[T, T, T, F, F]` |
|
||
| 1 | ✅ | 3 | 2, 3, 4 | `[T, T, T, T, T]` |
|
||
| 2 | ✅ | 1 | 3 | `[T, T, T, T, T]` |
|
||
| 3 | ✅ | 1 | 4 | `[T, T, T, T, T]` |
|
||
| 4 | ✅ | 4 | — | `[T, T, T, T, T]` |
|
||
|
||
以 `nums = [3,2,1,0,4]` 为例：
|
||
|
||
| j | dp[j] | nums[j] | 被标记为 true 的位置 | dp 数组状态 |
|
||
|---|-------|---------|-------------------|------------|
|
||
| 0 | ✅ | 3 | 1, 2, 3 | `[T, T, T, T, F]` |
|
||
| 1 | ✅ | 2 | 2, 3 | `[T, T, T, T, F]` |
|
||
| 2 | ✅ | 1 | 3 | `[T, T, T, T, F]` |
|
||
| 3 | ✅ | 0 | （无） | `[T, T, T, T, F]` |
|
||
| 4 | ❌ | — | — | **返回 false** |
|
||
|
||
- **时间复杂度：O(n²)** — 两层循环，内层最多遍历 nums[j] 次
|
||
- **空间复杂度：O(n)** — dp 数组
|
||
|
||
这个方法正确但不够优雅。我们真的需要记录每个位置的可达性吗？
|
||
|
||
> [!tip] 🔑 洞察
|
||
> 我们不关心"每个位置是否可达"，只关心"**当前最远能到哪里**"。只要这个最远距离在遍历过程中没有被卡住（即不会停在某个 0 的位置无法前进），就说明终点一定可达。这把我们从一个布尔问题变成了一个单变量问题。
|
||
|
||
### 方法三：贪心算法 ⭐
|
||
|
||
与其维护整个 dp 数组，不如用一个变量 `maxReach` 记录**从任意已访问位置出发，能到达的最远索引**。
|
||
|
||
> [!info] 🎯 核心思想
|
||
> 从左到右遍历数组，对于每个能到达的位置 `i`，更新 `maxReach = max(maxReach, i + nums[i])`。如果发现 `i > maxReach`，说明当前位置已经无法到达，返回 `false`。如果在遍历开始前 `maxReach >= n - 1`，直接返回 `true`。
|
||
|
||
> [!abstract] 🔬 正确性证明
|
||
>
|
||
> **不变式**：在遍历到下标 `i` 之前，`maxReach` 记录了从索引 `0..i-1` 中任意一个位置出发能到达的最远索引。
|
||
>
|
||
> 初始时，`maxReach = 0`（起点本身可达），不变式成立。
|
||
>
|
||
> 归纳步骤：假设在遍历到 `i` 时不变式成立。
|
||
>
|
||
> - **情况 1：`i > maxReach`** — 说明从起点出发无论如何都到不了位置 `i`，更不用说后面的位置了 → 返回 `false`。
|
||
> - **情况 2：`i <= maxReach`** — 位置 `i` 可达，从 `i` 能到达的最远位置是 `i + nums[i]`。更新 `maxReach = max(maxReach, i + nums[i])`，不变式对 `i+1` 依然成立。
|
||
> - **提前终止**：如果 `maxReach >= n - 1`，说明终点已经在可达范围内 → 返回 `true`。
|
||
>
|
||
> 因为 `i` 是从左到右线性递增的，且每次更新的 `maxReach` 是非递减的，所以最终一定能得到正确答案。证毕。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["开始\nmaxReach = 0"] --> B{"n == 1?"}
|
||
B -->|"是"| Z["返回 true"]
|
||
B -->|"否"| C["for i = 0 to n-1"]
|
||
C --> D{"i > maxReach?"}
|
||
D -->|"是"| Y["返回 false"]
|
||
D -->|"否"| E["maxReach = max(maxReach,\n i + nums[i])"]
|
||
E --> F{"maxReach >= n-1?"}
|
||
F -->|"是"| X["返回 true"]
|
||
F -->|"否"| G{继续下一轮?}
|
||
G -->|"是"| C
|
||
G -->|"否"| Y
|
||
```
|
||
|
||
#### 逐步推演
|
||
|
||
以 `nums = [2, 3, 1, 1, 4]` 为例：
|
||
|
||
| i | nums[i] | i ≤ maxReach? | i + nums[i] | maxReach | 说明 |
|
||
|---|---------|---------------|-------------|----------|------|
|
||
| 0 | 2 | ✅ 0 ≤ 0 | 0 + 2 = 2 | 2 | 从起点能跳到 0→1 或 0→2 |
|
||
| 1 | 3 | ✅ 1 ≤ 2 | 1 + 3 = 4 | 4 | 从位置 1 能直接跳到末尾！ |
|
||
| — | — | — | — | — | **maxReach(4) ≥ n-1(4)，返回 true** |
|
||
|
||
以 `nums = [3, 2, 1, 0, 4]` 为例：
|
||
|
||
| i | nums[i] | i ≤ maxReach? | i + nums[i] | maxReach | 说明 |
|
||
|---|---------|---------------|-------------|----------|------|
|
||
| 0 | 3 | ✅ 0 ≤ 0 | 0 + 3 = 3 | 3 | 最远能到索引 3 |
|
||
| 1 | 2 | ✅ 1 ≤ 3 | 1 + 2 = 3 | 3 | 从位置 1 最远也是到索引 3 |
|
||
| 2 | 1 | ✅ 2 ≤ 3 | 2 + 1 = 3 | 3 | 从位置 2 最远还是到索引 3 |
|
||
| 3 | 0 | ✅ 3 ≤ 3 | 3 + 0 = 3 | 3 | 位置 3 的跳跃长度为 0！陷入僵局 |
|
||
| 4 | — | ❌ 4 > 3 | — | — | 位置 4 不可达！**返回 false** |
|
||
|
||
注意到这个案例中的致命陷阱：**位置 3 的值是 0，它像一个"断头路"**。当你到达索引 3 时，再也跳不出去。而贪心策略通过追踪 `maxReach`，在遍历时发现没有任何前驱位置能把边界推到 4 以上，从而识别出这个死胡同。
|
||
|
||
- **时间复杂度：O(n)** — 只需一次遍历
|
||
- **空间复杂度：O(1)** — 只使用一个整型变量
|
||
|
||
> [!note] 🐹 与买卖股票Ⅰ的联系
|
||
> 本题的贪心思路与 `14-买卖股票的最佳时机`（单指针贪心）有异曲同工之妙：都是在遍历过程中维护一个"全局最优信息"（一个是价格差最小值，一个是可达最远距离），用 O(1) 空间完成决策。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
// 伪代码模板
|
||
maxReach = 0
|
||
for i from 0 to n-1:
|
||
// 如果当前位置已经超出可达范围，无法继续
|
||
if i > maxReach:
|
||
return false
|
||
|
||
// 更新能到达的最远位置
|
||
maxReach = max(maxReach, i + nums[i])
|
||
|
||
// 优化：如果已经可以到达终点，提前退出
|
||
if maxReach >= n - 1:
|
||
return true
|
||
|
||
return maxReach >= n - 1
|
||
```
|
||
|
||
Go 语言中可以用内置的 `max` 函数简化表达式（Go 1.21+）。注意：题目保证 `n >= 1`，当 `n == 1` 时起点就是终点，直接返回 `true`。
|
||
|
||
```go
|
||
// Go 风格精简版骨架
|
||
func canJump(nums []int) bool {
|
||
maxReach := 0
|
||
for i, v := range nums {
|
||
if i > maxReach {
|
||
return false
|
||
}
|
||
maxReach = max(maxReach, i+v)
|
||
if maxReach >= len(nums)-1 {
|
||
return true
|
||
}
|
||
}
|
||
return true
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：可达范围贪心（Reachable Range Greedy）
|
||
> "追踪最远边界"是一种通用策略，适用于各类"能否到达/能否覆盖"的问题。典型特征：① 每个位置提供一个"能力值"（如跳跃长度、活动范围半径）；② 问题本质是判断目标点是否落在这些能力的并集内。
|
||
|
||
> [!warning] ⚠️ 与跳跃游戏 II 的区别
|
||
> 本题（55题）只问"能不能到"，而 45题（跳跃游戏 II）问"最少跳几次"。后者需要在每个可达范围内额外记录"当前步数内的最远边界"来计数，属于同一种贪心框架的扩展版本。建议两题对照练习。
|
||
|
||
> [!danger] ⚠️ 常见误区
|
||
> 有人想到从后往前贪心：找离终点最近的、能一步跳到终点的位置，再往回找。这个方法也正确，但对实现者来说思维负担更大——正向遍历只需维护一个变量，反向遍历则需要多次定位。面试推荐正向写法。
|
||
|
||
> [!quote] 🧠 为什么这里贪心是正确的？
|
||
> 贪心之所以危险，是因为局部最优不等于全局最优。但在本题中，"扩大最远可达范围"是一个**单调不降**的操作——任何额外的跳跃选择不可能让最远边界变小。也就是说，每一步我们都选择了能让未来选项最大化的一步，这正是贪心成立的充分条件。
|
||
|
||
> [!summary] 📊 两种跳跃游戏对比
|
||
> | 特征 | 55. Jump Game | 45. Jump Game II |
|
||
> |------|--------------|-----------------|
|
||
> | 问题类型 | 可行性判定 | 最优值求解 |
|
||
> | 贪心策略 | 追踪最远边界 | 每步限制内尽可能推远 |
|
||
> | 时间复杂度 | O(n) | O(n) |
|
||
> | 是否需要计数器 | 不需要 | 需要 |
|
||
|
||
> [!example] 🔗 相关变种
|
||
> - [45. 跳跃游戏 II](./79-跳跃游戏 II.md) —— 求最少跳跃次数
|
||
> - [130. 被围绕的区域](../深度优先搜索/) —— 同样是连通性/可达性问题
|
||
> - [862. 和至少为 K 的最短子数组](../队列/) —— 滑动窗口 + 单调队列拓展
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
// canJump returns whether it's possible to reach the last index
|
||
// by jumping from index 0, where each element represents the maximum jump length.
|
||
func canJump(nums []int) bool {
|
||
// ── Step 1: 边界处理 ──
|
||
// 只有一个元素时，起点就是终点
|
||
if len(nums) == 1 {
|
||
return true
|
||
}
|
||
|
||
// ── Step 2: 初始化最远可达位置 ──
|
||
maxReach := 0 // 从已访问位置出发能到达的最远索引
|
||
|
||
// ── Step 3: 一次遍历，实时更新最远边界 ──
|
||
for i, v := range nums {
|
||
// 如果当前位置已经超出可达范围，说明遇到了断点
|
||
if i > maxReach {
|
||
return false
|
||
}
|
||
|
||
// 更新最远可达位置
|
||
maxReach = max(maxReach, i+v)
|
||
|
||
// 优化：提前终止 —— 已经可以覆盖终点
|
||
if maxReach >= len(nums)-1 {
|
||
return true
|
||
}
|
||
}
|
||
|
||
return true
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> - **LeetCode 第 55 题**，通过率约 35%，中等难度经典题。
|
||
> - `nums = [2,3,1,1,4]` → `true`，在 i=1 时 maxReach 达到 4，提前返回。
|
||
> - `nums = [3,2,1,0,4]` → `false`，遍历到 i=4 时发现 4 > maxReach(3)，返回 false。
|
||
> - `nums = [0]` → `true`，边界情况：单个元素，起点即终点。
|
||
> - `nums = [2,0]` → `true`，从位置 0 跳 2 步即可覆盖索引 1。
|
||
> - **性能**：时间 O(n)，空间 O(1)。实际运行通常在 0ms ~ 2ms 之间（取决于数据规模）。
|