跳跃游戏 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i]且i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
示例 1
示例 2
模拟答题者思考
1. 最直接：从每个位置 DFS/BFS 枚举所有合法跳跃路径，记录到达 n-1 的最短路径，状态空间指数级，n=10⁴ 会超时。
2. 重复在哪里？「到位置 i 最少几步」会被反复计算——典型 DP：dp[i] = min(dp[j]+1) 对所有 j<i 且 j+nums[j]≥i，朴素 O(n²)。
3. 换个视角：不是「到某点最少几步」，而是按跳跃次数分层——第 0 跳能覆盖 [0..end₀]，在第 0 跳可达范围内再跳一次能覆盖 [0..end₁]……层数就是答案。
4. 贪心关键：扫描当前层 [0..end] 时只需维护「再跳一步最远能到哪」farthest；当 i 扫到本层右边界 end，说明下一跳不可避免，steps++ 并把 end 扩展到 farthest。
5. 正确性直觉：在当前层内无论从哪里再跳，最远不超过 farthest；推迟增加 steps 不会让下一层边界更大，因此在 i==end 时结算一层是最优的。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
steps | int | 定义：从起点到当前「跳跃层」已使用的最小跳跃次数 维护：当扫描指针 i 触及当前层右边界 end 时，说明必须再跳一层，steps += 1更新：循环结束后 steps 即为到达 n-1 的最少跳跃数 |
end | int | 定义：仅用当前 steps 次跳跃所能到达的最远下标（当前层的右边界）维护：初始 end=0；每当 i==end 完成一层扫描后，令 end = farthest 扩展到下一层更新： end 单调不减，且题目保证可达，最终会 ≥ n-1 |
farthest | int | 定义：在当前层内任取起点再跳一步，能到达的最远下标（下一层的候选右边界） 维护：遍历 i ∈ [0, end] 时持续 farthest = max(farthest, i + nums[i])更新：一层扫完时把 farthest 赋给 end，作为下一层边界 |
i | int | 定义：从左到右扫描的下标，代表「当前层里正在考察的落脚点」 维护： for i in range(n-1)，最后一格无需再跳更新：每轮用 nums[i] 更新 farthest，并在 i==end 时结算一层 |
落码步骤
1. 初始化 steps=0, end=0, farthest=0
2. 遍历 i 从 0 到 n-2（最后一格不必再跳）
3. 更新 farthest = max(farthest, i + nums[i])
4. 若 i == end：说明当前层扫完，steps += 1，end = farthest
5. 返回 steps
代码实现
class Solution:
def jump(self, nums: List[int]) -> int:
steps = 0
end = 0 # 当前跳跃次数能到达的最远下标
farthest = 0 # 下一跳能到达的最远下标
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end:
steps += 1
end = farthest
return stepsclass Solution {
public:
int jump(vector<int>& nums) {
int steps = 0, end = 0, farthest = 0;
for (int i = 0; i < nums.size() - 1; i++) {
farthest = max(farthest, i + nums[i]);
if (i == end) {
steps++;
end = farthest;
}
}
return steps;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
循环应到 n-2 而非 n-1：已在最后一格时无需再跳，多扫一轮可能多计一次 steps。
本题求最少跳跃次数，与 #55「跳跃游戏」（判断能否到达）不同；能到达时最少步数贪心有效，不能混用「能跳就跳最远」的写法。
必须在 i == end 时再 steps++，而不是每更新 farthest 就加；否则把「层内扫描」和「结算一层」混在一起会算错。
必测边界 Case
nums = [0] → 0（已在终点，无需跳跃）
nums = [2, 1] → 1（从下标 0 直接跳到末尾）
nums = [1, 1, 1, 1] → 3（每次最多跳 1，需 3 次）
nums = [2, 3, 0, 1, 4] → 2（中间 0 不影响层边界扩展）
nums = [5, 4, 3, 2, 1] → 1（第一步即可覆盖全程）