LC45　跳跃游戏 II¶

中等通过率 46%python3核心代码模式贪心算法样例通过牛客 AC贪心数组动态规划

讲解章节：贪心

一句话

按「第几步能到」分层，扫到当前层的右边界就结算一步，层数即答案。

解题思路¶

这题考什么¶

把下标看成图的结点，从 i 能一步走到 i+1 到 i+nums[i] 的任意一个，「最少跳几次」就是从 0 到 n-1 的最短路。边权全为 1，最短路等于 BFS 的层数。真去建图跑 BFS 是 O(总边数) = O(n 乘 max(nums))，n = 1e4、nums[i] 到 1000 时约 1e7 条边，而且要存邻接结构，完全没必要——因为这张图有极强的结构：

**第 t 层（恰好 t 步能到达的下标集合）连同前面各层，合起来是一段连续前缀。**

理由和 LC55 跳跃游戏是同一条：站在 p 能跳到 p 后面那一整段里的任意一个，不会漏掉中间的下标。于是「t 步以内可达」的集合就是 [0, end_t]，每一层只需要记住它的右边界，不必存出整个集合。

一趟扫描就能推出所有层的右边界：

cur_end  当前层的右边界，也就是「已用步数 steps 步最远能到哪」
farthest 扫描途中见过的最大 i + nums[i]，即下一层的右边界

从左往右扫 i：先用 i 更新 farthest；
当 i 走到 cur_end，说明当前层已经全部看完，
必须再跳一步才能继续  ->  steps += 1，cur_end = farthest。

结算时机是全题的关键：在跨出当前层的那一刻记一步，而不是每到一个下标就记。这条贪心的可行性论据是——要走到 cur_end 右边的任何位置，至少得从当前层里的某个点再跳一次，所以 steps 不可能更小；而当前层里所有点的跳跃能力都已经并进 farthest，所以再跳一次能到的最远处正是 farthest，steps 也不会更大。上下界一夹，这个计数就是最优的。贪心的这类「按可行域分层」论证见贪心。

要区分开一个错误的贪心：「每步都跳满 nums[i] 格」。 nums = [2,3,1,1,4] 按这个策略是 0 -> 2 -> 3 -> 4，要 3 步，而正确答案是 2（0 -> 1 -> 4）。跳得远不等于跳得好，真正该最大化的是「下一层能覆盖到哪」，那需要把整层的候选都看一遍。

数据规模与复杂度¶

1 <= nums.length <= 1e4，0 <= nums[i] <= 1000，题目保证一定能到达 n-1。时间 O(n)：一趟扫描，每个下标做常数次比较；空间 O(1)，只有三个整数。动态规划的写法（dp[i] = 到 i 的最少步数，从 i 往后逐格松弛）是 O(n 乘 max(nums)) = 1e4 乘 1e3 = 1e7 次转移，Python 下要按秒计，而贪心把它压到 1e4 次。

坑在哪¶

循环只扫到 n-2，不能扫到 n-1。走到最后一个下标时任务已经完成，若它恰好等于 cur_end，还会再触发一次结算，答案凭空多 1。 nums = [2,3,1,1,4] 扫到 n-1 会返回 3 而不是 2。
steps 是在「i 追上 cur_end」时加的，不是每次跳跃动作时加的。代码里没有任何「跳到哪个下标」的模拟——层数是数出来的，不是走出来的。
更新 farthest 必须在结算之前。同一轮里先扩张再判边界，结算时 farthest 才包含了当前层最后一个点的贡献；顺序反了，新的 cur_end 会漏掉这个点，层数被高估。
结算时用的是 farthest 而不是 i + nums[i]。当前层的最优后继未必来自最后一个点， [2,3,1,1,4] 里 cur_end = 2 那次结算就靠 i = 1 贡献的 farthest = 4。
n == 1 时答案是 0：起点就是终点，一步都不用跳。本题解不需要特判， range(n - 1) 是空的，直接返回初值 0。
题目保证一定可达，所以不必考虑 cur_end 卡死（farthest 不再增长）的情形。若换成不保证可达的题，那一层要额外判 farthest <= i 并返回无解。
元素可以是 0。它只是对 farthest 没有贡献，不会让本题解出错，因为可达性由题目担保。

样例复核¶

nums = [2,3,1,1,4]，n = 5，扫 i = 0..3：

i=0：farthest = 0+2 = 2；i == cur_end(0) -> steps = 1，cur_end = 2
i=1：farthest = max(2, 1+3) = 4；i 未到 cur_end
i=2：farthest = max(4, 2+1) = 4；i == cur_end(2) -> steps = 2，cur_end = 4
i=3：farthest = max(4, 3+1) = 4；i 未到 cur_end
返回 2，与样例一致。层的含义对得上：0 步到 {0}，1 步内到 [0,2]，2 步内到 [0,4]。

nums = [2,3,0,1,4] 走的是同一笔账（i=2 处 farthest 保持 4），同样返回 2。

参考实现¶

solutions/leetcode/LC45/sol.py
from typing import List, Optional


class Solution:
    def jump(self, nums: List[int]) -> int:
        # steps 是已经结算的层数，也就是答案
        steps = 0
        # cur_end：当前层的右边界，即「用 steps 步最远能到的下标」。初值 0 表示
        # 0 步能到的只有起点本身
        cur_end = 0
        # farthest：扫描途中见过的最大 i + nums[i]，也就是下一层的右边界
        farthest = 0
        # 只扫到 n-2。走到最后一个下标时任务已完成，再让它触发一次结算，
        # 层数就会凭空多 1。n == 1 时这个范围是空的，直接返回 0
        for i in range(len(nums) - 1):
            # 先扩张再判边界：这样结算那一刻 farthest 已经包含当前层最后一个点的贡献
            if i + nums[i] > farthest:
                farthest = i + nums[i]
            # i 追上当前层的右边界，说明这一层的点全部看过了；
            # 想再往右走必须从这一层里跳出去，于是记一步，边界推进到下一层
            if i == cur_end:
                steps += 1
                # 用 farthest 而不是 i + nums[i]：当前层的最优后继未必来自最后一个点
                cur_end = farthest
        return steps

LC45 跳跃游戏 II¶