LC55　跳跃游戏¶

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

讲解章节：贪心

一句话

一趟扫描维护「最远能到哪」，走到某个下标时它已超出可达范围就判负。

解题思路¶

这题考什么¶

真去搜索「先跳几步、再跳几步」会爆炸：每个位置有 nums[i] 种选择， n = 1e4 时分支数天文级别。让这题塌成一趟扫描的，是下面这条结构性质：

**可达集合永远是一段从 0 开始的连续前缀 [0, reach]。**

证明只用一句话：站在 p 能一步跳到 p+1, p+2, ..., p+nums[p] 中的任意一个，也就是说到得了 p 就到得了 p 后面那一整段里的每个下标，中间不会漏。从 0 出发按这个规则不断扩张，可达的下标不可能出现空洞。

有了「可达集合是前缀」，只需要维护这个前缀的右端 reach = 最远可达下标：

从左往右扫每个下标 i；
若 i > reach，说明 i 已经掉出可达前缀，它和它后面的都到不了 -> 返回 False；
否则 i 可达，用它更新 reach = max(reach, i + nums[i])。

这段贪心的可行性论据是：更新 reach 时只用到「i 可达」这一个前提，而扫描顺序保证了在处理 i 之前，所有能跳到 i 的位置都已经贡献过了。因此循环结束时 reach 就是真正的最远可达下标，中途没有被低估过。这属于贪心里最典型的「维护一个可行域边界」的形态，正确性来自问题本身的结构而非交换论证，见贪心。

扫完全程都没有掉出可达范围，说明每个下标（含 n-1）都可达，返回 True。

数据规模与复杂度¶

1 <= nums.length <= 1e4，0 <= nums[i] <= 1e5。注意跳跃长度的上界 1e5 远大于数组长度，所以 i + nums[i] 经常远远超出 n - 1，这不是错误，只是「早就够得着终点了」。时间 O(n)：一趟扫描，每个下标做常数次比较。空间 O(1)。动态规划的写法（dp[i] 表示 i 是否可达，逐个从前面的可达位置转移）是 O(n 乘 max(nums)) = 1e4 乘 1e5 = 1e9，Python 下必然超时；贪心之所以能省掉这一层，正是因为可达集合是连续前缀，不必逐点记录。

坑在哪¶

判负的条件是 i > reach，用严格大于。写成 i >= reach 会把「恰好踩在最远点上」误判成失败：nums = [1,1,1] 扫到 i = 1 时 reach 正是 1，那一步是合法的落点，却会返回 False。
更新与判断的先后不能反。必须先确认 i 可达，再拿 nums[i] 去扩张 reach—— 一个不可达的位置无权贡献跳跃距离。nums = [3,2,1,0,4] 里下标 4 的 nums[4] = 4 很大，但它根本到不了，先更新后判断会让 reach 被它撑到 8，错误地返回 True。
元素可以是 0，这是本题唯一的失败来源：踩进一个 0 且它恰好是当前的 reach，之后 reach 再也不增长，下一个 i 就掉出范围。样例 2 的 [3,2,1,0,4] 正是如此。
reach 初值取 0 而不是 nums[0]。0 表示「起点自己可达」，初值写成 nums[0] 会在 n == 1 时凭空放大可达范围（虽然此时答案照样是 True），更要紧的是它把「下标」和「跳跃长度」两种量混为一谈，扩展到别的题就会错。
n == 1 时不需要跳，答案是 True。本题解不需要特判：i = 0 时 0 > 0 不成立，循环走完直接返回 True。
返回布尔值，不是 0 / 1，也不是能到达的下标。判题严格比对结构。
扫到 reach >= n - 1 时其实可以提前返回 True。本题解不写这个优化：它不改变最坏复杂度，却多一处边界判断，读起来反而更难确认正确性。

样例复核¶

nums = [2,3,1,1,4]：

i=0 reach=0 -> 0 不大于 0，reach = max(0, 0+2) = 2
i=1 reach=2 -> 可达，reach = max(2, 1+3) = 4
i=2 reach=4 -> 可达，reach = max(4, 2+1) = 4
i=3、i=4 同样可达，reach 保持 4。
扫完返回 True，与样例一致。

nums = [3,2,1,0,4]：

i=0 reach 变 3；i=1 -> max(3, 3) = 3；i=2 -> max(3, 3) = 3；
i=3 -> nums[3] = 0，max(3, 3) = 3；
i=4 时 4 > 3，掉出可达前缀，返回 False，与样例一致。

参考实现¶

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


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # reach 是当前已知的最远可达下标。可达集合永远是连续前缀 [0, reach]，
        # 所以一个右端就足以描述它。初值 0 的含义是「起点自己可达」，
        # 它是下标而不是跳跃长度，写成 nums[0] 就把两种量混为一谈了
        reach = 0
        for i, step in enumerate(nums):
            # 先判可达再扩张：不可达的位置无权贡献它的跳跃长度。
            # 顺序反了的话，[3,2,1,0,4] 里够不着的 nums[4] = 4 会把 reach 撑到 8
            if i > reach:
                # 严格大于才算掉出前缀。i == reach 是合法落点，
                # 写成 >= 会把 [1,1,1] 这类刚好踩在边界上的情形误判成失败
                return False
            # i 可达，于是从 i 起跳能摸到 i + step；扫描顺序保证处理到 i 时
            # 所有能跳到 i 的位置都已贡献过，reach 不会被低估
            if i + step > reach:
                reach = i + step
        # 全程没有掉出可达前缀，说明每个下标（含最后一个）都到得了
        return True

LC55 跳跃游戏¶