LeetCode 45. 跳跃游戏 II
题目描述
题意分析
数组
nums[i]表示从下标i出发最多可以向右跳多远，可以选择不超过这个长度的任意合法落点。起点为下标0，目标为下标n - 1，返回到达终点所需的最少跳跃次数。题目保证至少有一条路线能到终点，但不表示每个中间位置都值得跳过去。要最小化的是跳跃次数，不是路程，也不是某一次跳得尽可能远。数组只有一个元素时已经在终点，答案为零。
解法：贪心维护当前覆盖边界
核心思路
[!blue]
把各下标看作位置，从一个位置能用一跳到达的一段区间看作相邻位置。按跳跃次数从少到多扩展，就相当于 BFS：先考虑零跳可达的起点，再考虑一跳可达的位置，之后才考虑两跳可达的位置。
这里每次可以选择最大长度以内的任意落点，因此可达范围是连续的。用
curEnd表示当前跳数能够覆盖的最右边界，扫描本层全部候选出发点，并用nextEnd记录它们再跳一次所能覆盖的最远位置。当前位置提供的范围右端是i + nums[i]，对这些右端取最大值即可，无需把所有落点逐个放进队列。在到达
curEnd之前，本层还有候选没有检查，不能提前选定下一跳。先把当前下标的贡献更新到nextEnd，再检查i == curEnd；相等时才说明本层全部处理完，可以令steps++，把curEnd推进到nextEnd。当前步数无法越过旧边界，任何更远的目标都至少需要再跳一次；而下一层边界来自本层真实可达位置的跳跃，所以其中的目标确实能用多一次跳跃到达。逐层扩展第一次覆盖终点时，得到的就是最少次数。
nextEnd是对所有候选的汇总，不代表必须真的跳到当前最远位置。循环只扫描到
n - 2。终点只需被到达，不必作为出发点再扩展一次；一旦当前边界已经覆盖终点，剩余扫描也不会再经过需要结算的边界。题目保证可达，所以在终点之前不会陷入无法扩张的层。
解题步骤
- 初始化
steps = 0，curEnd = nextEnd = 0，零跳时只覆盖起点。- 从下标
0扫描到n - 2，先更新nextEnd = max(nextEnd, i + nums[i])。- 若
i == curEnd，本层扫描完毕，将跳数加一，并令curEnd = nextEnd。- 返回累计跳数；单元素输入不会进入循环，直接返回零。
代码实现
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)$，只维护跳数、当前层边界和下一层最远边界。
关键点总结
[!green]
- 按最少跳数逐层扩展，可达位置连续，能够用边界代替显式队列。
- 当前层全部扫描后才结算下一跳，比较的是所有落点的后续覆盖能力。
curEnd控制何时增加跳数，nextEnd汇总下一层，两个变量不能混用。
易错点总结
[!yellow]
- 每次直接跳到最远落点，可能错过更有后续跳跃能力的位置；本解法保留整层候选。
- 在更新
nextEnd之前结算层边界，会漏掉本层最后一个位置能提供的范围。- 用当前位置的右端直接覆盖
nextEnd，会丢掉之前更远的候选，应始终取最大值。- 循环包含终点，会把已经到达终点后的一次扩展也算成跳跃。
- 只比较
nums[i]大小忽略了起跳位置，真正的覆盖右端是i + nums[i]。- 该实现依赖题目保证终点可达；不能把遍历次数或最后的跳数当作不可达输入的判定结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 55. 跳跃游戏 | 中等 | 原题只判断能否到终点，本题按当前一步可覆盖的边界分层，统计最少跳跃次数。 |
| 1024. 视频拼接 | 中等 | 同样贪心扩张当前可达右边界，原题用视频区间覆盖目标，本题用跳跃区间覆盖终点。 |