题型地图 56天全屏 141题

当前：LC45 · 跳跃游戏 II · 峡谷跳跃救援 · 首次出现于 Day 41 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

19 / 141回到 Day 41 卡片 141 题索引

LC45

跳跃游戏 II：最少几次跳过峡谷？

峡谷跳跃救援 · 最少跃迁

每个悬浮平台上的数字不是必须跳这么远，而是最多能跳这么远。救援机器人从 0 号平台出发，要用最少跃迁次数抵达终点传送门。

主动画 · nums

23114

最少跃迁

时间 O(n)空间 O(1)三层状态：jumps · curEnd · farthest

核心心智（必记）

这题不是每一步都马上选择落点，而是把当前跳数能覆盖的一整层扫描完，再决定下一跳的最远边界。

LC55 · 能不能到？

返回 bool。只维护一个 reach：安全区能扩到多远。

LC45 · 最少几跳？（本题）

返回 int。多维护 curEnd（当前跳覆盖右边界）和 farthest（下一跳最远边界）。

初始化Step 1 / 10

3D 峡谷平台主舞台

jumps=0 · curEnd=0 · farthest=0

curEnd=0

farthest=0

起点

#02

#13

#21

#31

传送门

#44

初始化：救援机器人站在 0 号悬浮平台。jumps = 0（还没正式跃迁），curEnd = 0（当前 0 跳能覆盖的最右边界就是起点），farthest = 0（下一跳最远边界还没扫描出来）。

蓝罩 · 当前跳可覆盖层红柱 · curEnd（当前跳右边界）绿柱 · farthest（下一跳最远边界）金弧 · i+nums[i] 候选机器人 · 扫描指针 i

Go 代码 · 逐行高亮

行 2, 3, 4

1func jump(nums []int) int {
2    jumps := 0
3    curEnd := 0
4    farthest := 0
5 
6    for i := 0; i < len(nums)-1; i++ {
7        farthest = max(farthest, i+nums[i])
8 
9        if i == curEnd {
10            jumps++
11            curEnd = farthest
12        }
13    }
14 
15    return jumps
16}

机器状态卡片

i（扫描指针）

—

nums[i]

—

i + nums[i]

—

farthest

curEnd

jumps

jumps — 已经用了几次正式跃迁（层数计数器）。

curEnd — 当前跳数能覆盖到的最右边界，不是机器人当前脚下位置。

farthest — 扫描当前层时发现的下一跳最远边界，不是已经到达的位置。

右侧分镜 · 这一帧在讲什么

这题不是每一步都马上选择落点，而是把当前跳数能覆盖的一整层扫描完，再决定下一跳的最远边界。

jumps=0 · curEnd=0 · farthest=0

执行轨迹表

点击行跳转

Step	i	farthest	curEnd	jumps	i==curEnd?	动作
0	—	0 = 0	0	0	—	初始化
1	—	0 = 0	0	0	—	对比 LC55
2	0	0 → 2	0	0	no	更新 farthest
3	0	2 = 2	0 → 2	0 → 1	yes · jumps++	层扫完 · jumps++
4	1	2 → 4	2	1	no	更新 farthest
5	1	4 = 4	2	1	no	层内继续扫
6	2	4 = 4	2	1	no	更新 farthest
7	2	4 = 4	2 → 4	1 → 2	yes · jumps++	层扫完 · jumps++
8	4	4 = 4	4	2	no	循环边界说明
9	—	4 = 4	4	2	—	返回答案

分镜解释区

初始化

i=0：farthest→2，层边界 jumps=1

扫描 i=0：从平台 0 最多能跃到 0+nums[0]=0+2=2。farthest = max(0, 2) = 2。这是在为「下一跳」收集最远边界，不代表机器人已经站在 2。

i=1：farthest→4，仍在第 1 跳层内

扫描 i=1：从平台 1 最多能跃到 1+nums[1]=1+3=4。farthest = max(2, 4) = 4。这是在为「下一跳」收集最远边界，不代表机器人已经站在 4。

i=2：farthest 保持 4，jumps=2

扫描 i=2：候选边界 3 不比旧 farthest=4 更远，farthest 保持 4。继续把当前层扫完。

循环止于 len-2

循环条件是 i < len(nums)-1，只扫到 index 3。到最后一个平台 index 4 时任务已经结束，不需要再从终点往外跳；若写到 i < len(nums)，可能在终点多算一次 jumps。

答案 2

curEnd=4 已覆盖终点 index 4。最少跃迁次数 jumps = 2。主动画 nums=[2,3,1,1,4] 的答案是 2。

面试回答模板

我用贪心维护两个边界。curEnd 表示当前跳数能到达的最右位置，farthest 表示扫描当前范围时，下一跳能到达的最远位置。遍历数组时不断更新 farthest；当 i 到达 curEnd，说明当前这一跳覆盖的范围已经扫描完，需要增加一次跳跃，并把 curEnd 推进到 farthest。因为每一跳都在当前可达范围内选择能扩张最远的下一层边界，所以跳数最少。时间 O(n)，空间 O(1)。

常见误区

误区一：以为每一步都要立刻选择具体落点
算法从不枚举「这一跳落在哪一格」，只在一层内扫描所有可达位置，用 farthest 记录下一层最远边界。
误区二：把 farthest 当成已经到达的位置
farthest 是「下一跳最远能到哪」的预告，机器人扫描指针 i 可以远小于 farthest。
误区三：不知道为什么 i == curEnd 时才 jumps++
i 走到 curEnd 表示「当前跳数能覆盖的范围」右边界已经扫完，必须开启下一跳，所以 jumps++ 并把 curEnd 设为 farthest。
误区四：循环写到 len(nums)-1 导致多算
终点已经是任务结束位置，不需要再从终点往外跳；for 只到 len(nums)-2，否则可能在终点多算一次 jumps。