LeetCode 45. 跳跃游戏 II
目录
题目描述
题意分析
给定一个非负整数数组
nums，初始站在下标0。站在下标i时，可以跳到i + 1到i + nums[i]之间的任意一个下标——注意是「最多跳这么远」而不是「必须跳这么远」，中间任何一个落点都合法。要求返回到达最后一个下标n - 1所需的最少跳跃次数。题面里有两个约束信号必须抓住。第一，题目保证一定能到达终点，也就是说不存在返回
-1的分支，也不会出现「卡在某个0上」的情况需要判断，可行性完全不用操心，全部注意力放在「最少」上。第二，求的是次数而不是路径，只要数字对，具体跳了哪几个点无所谓，这就为「不记录路径、只维护范围」留下了空间。数据规模上，
n可以到一万量级，值域是0到一千，$O(n^2)$ 未必超时但也没有余量，理想目标是线性。边界要考虑几处：数组长度为
1时已经站在终点，答案是0，绝不能返回1；只要不在终点，从当前位置一定跳得动（由保证可达推出），所以不必担心nums[i] == 0造成死路；nums[i]可能很大以至于一步就跨过末尾，这属于合法情况，不算越界。「答案是次数」「保证可达」「只问最少不问路径」这三点叠在一起，说明真正要回答的问题其实是：跳
k次最远能覆盖到哪里——一旦这个覆盖范围盖住了n - 1，k就是答案。
解法：贪心维护当前覆盖边界
核心思路
问题关键：不能真的决定每一步落在哪里。一次跳跃能够到达一段连续区间，求最少次数等价于按 BFS 层次追问：跳
k次最远能覆盖到哪个下标。为什么选贪心：若用 DP 枚举每个位置能跳到的所有后继，最坏需要 $O(n^2)$。同一跳数可达的位置是一段连续区间，因此无需保存每个位置的最少跳数，只需扫描这一层，并取所有
i + nums[i]的最大值作为下一层右边界。状态与不变量：
steps是当前已确定的跳数；curEnd是跳steps次能到达的最远位置；nextEnd是扫描过的当前层位置再跳一次能到达的最远位置。扫描期间始终有i <= curEnd，题目保证可达，所以当前层不会断开。正确性：当
i == curEnd时，当前跳数能到达的所有位置都已扫描完。任何继续向右的方案都至少要再跳一次，因此steps++是必要的；而nextEnd汇总了这一层所有出发点的最远覆盖范围，更新curEnd = nextEnd又不会漏掉更优方案。逐层推进，第一次覆盖终点时得到的就是最少跳数。循环只遍历到
n - 2：终点不需要作为出发点。若扫描n - 1，它恰好等于层边界时会多计一次跳跃。
解题步骤
面试时可按下面 4 步口述：
- 初始化
steps = curEnd = nextEnd = 0，第 0 层只有起点。- 从下标
0扫到n - 2，用nextEnd = max(nextEnd, i + nums[i])收集下一层边界。- 当
i == curEnd，说明当前层扫描完毕，跳数加一，并把curEnd推进到nextEnd。- 扫描结束后返回
steps。例如
[2,3,1,1,4]：扫描i = 0后第一层边界为2，steps = 1；扫描完i = 1,2后下一层边界为4，steps = 2，已覆盖终点。
代码实现
class Solution {
public int jump(int[] nums) {
int steps = 0;
int curEnd = 0;
int nextEnd = 0;
for (int i = 0; i < nums.length - 1; i++) {
nextEnd = Math.max(nextEnd, i + nums[i]);
if (i == curEnd) {
steps++;
curEnd = nextEnd;
}
}
return steps;
}
}
func jump(nums []int) int {
steps := 0
curEnd := 0
nextEnd := 0
for i := 0; i < len(nums)-1; i++ {
if i+nums[i] > nextEnd {
nextEnd = i + nums[i]
}
if i == curEnd {
steps++
curEnd = nextEnd
}
}
return steps
}
复杂度分析
- 时间复杂度：$O(n)$。每个下标只扫描一次，边界只向右推进。
- 空间复杂度：$O(1)$。只维护跳数和两个边界。
关键点总结
- 这不是“每次跳到最远位置”，而是扫描当前层的所有候选落点，再确定下一层的最远边界。
curEnd与nextEnd分别表示当前层、下一层，不能合并成一个变量。- 到达
curEnd才结算一次跳跃，与 BFS 扫完一层后层数加一完全等价。- 与 55 题的区别：55 只判断可达性，维护一个最远位置即可；本题求最少步数，必须保留分层边界。
易错点总结
- 循环写到
n - 1会把“站在终点”再算成一次跳跃；[0]应返回0。- 必须先更新
nextEnd，再判断i == curEnd，否则会漏掉当前层最后一个位置的贡献。nextEnd必须取最大值，直接赋成i + nums[i]会被较短的跳跃覆盖。- 不要按
nums[i]最大选择落点，真正有意义的是覆盖终点i + nums[i]；边界贪心无需显式还原路径。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 55. 跳跃游戏 | 中等 | 只问可达性，单个最远边界即可，不需要分层 |
| 1306. 跳跃游戏 III | 中等 | 跳跃方向可左可右，范围不再连续，必须真的做 BFS 或 DFS |
| 1024. 视频拼接 | 中等 | 同样是最少段数覆盖，但区间任意给出，需先按左端点排序 |
| 134. 加油站 | 中等 | 前缀和视角的贪心，靠「起点可跳过一整段」剪枝而非分层 |