LeetCode 55 跳跃游戏：贪心算法如何将O(n²)优化到O(n)

LeetCode 55 跳跃游戏，一道让我当初刷到凌晨两点的题。如果你只看最终答案，贪心解法不过十行代码，O(n)时间、O(1)空间，简单到让人怀疑人生。但真正的难点从来不是背代码，而是搞明白“你凭什么想到用贪心”，以及面对面试官追问“为什么这样写一定对”时能不能讲得清楚。这篇文章打算把这题彻底拆开：先还原题面，再复盘暴力方案为什么会超时，然后给出贪心的完整思考链路和代码实现，最后整理我在本地调试和面试准备过程中踩过的坑、测过的边界用例，顺便把跳跃游戏II这个经典变体也带进来对比。适合刚开始刷算法题的新手，也适合想把这题讲透的求职者。

1. 先看懂题面：它到底在考什么

1.1 题意还原：不是“每次都跳那么多”，而是“最多能跳那么多”

题目本身很简短：给你一个非负整数数组 nums，你一开始站在下标 0 的位置，每个元素 nums[i] 表示从下标 i 出发“最多可以跳的长度”。注意这里的关键词是“最多”，也就是说你可以选择跳 0 步、1 步、2 步……直到 nums[i] 步。问你最终能不能跳到最后一个下标。

很多人第一次读题都会发生一个误解，以为 nums[i] 是一个固定步长，必须刚好跳那么多，这就把题目做歪了。比如 [2, 3, 1, 1, 4]，正确答案是 true。一种跳法是：从 0 跳到 1（用了 1 步，没超过 2），再从 1 跳到 4（用了 3 步，刚好等于 nums[1]）。但如果理解成必须跳满 nums[0]=2，那从 0 只能到 2，然后 nums[2]=1 只能到 3，nums[3]=1 到 4，也能到达，但换一种用例就区分不开了。

再看 [3, 2, 1, 0, 4] 这个经典反例：从 0 出发，最多跳 3 步，可以到 1、2、3；到了位置 3 之后，nums[3]=0，就卡死了。你可能会想，那我不去位置 3 不就行了？问题是位置 1 只能再跳 2 步，最远到 3；位置 2 只能再跳 1 步，最远到 3。所有路线的终点都是下标 3，而下标 3 是一个“死点”，所以整体返回 false。

我建议你拿到任何算法题，第一件事不是想解法，而是先在纸上把这两个例子手动跑一遍。手动模拟的过程中你会自然产生两个问题：第一，路径组合太多了，怎么高效判断？第二，位置 3 这种“死点”到底如何影响结果？这两个问题其实就是暴力解法和贪心解法之间的分水岭。

1.2 第一反应为什么会翻车：暴力搜索与指数爆炸

绝大多数人看到“能否到达”这种判定题，第一反应就是搜索。无非是：从当前位置出发，枚举跳 1 步、2 步、……直到 nums[i] 步，每个分支继续递归，只要有一条路径到达末尾就返回 true。听起来很直观，写出来也就二三十行，本地跑几个小例子也都对，一提交就超时。

超时的原因得从最坏情况分析。假设 nums 全是 9，每个节点的分支数量接近 9，递归树深度接近 n，整棵树的节点数量大约是 9 的 n 次方量级。哪怕限制了步数上限，复杂度依然是指数级的 O(k^n)，k 是数组中的最大跳跃步数。当数组长度到 10^5，这个量级约等于不可能。

有人会说我加一个 memo 数组，记录“从某个位置出发是否能到达终点”，避免重复计算。这样做能把复杂度降下来吗？确实能降，从指数降到多项式，但每个位置仍然要枚举它后面所有可达目标，总代价大约是所有位置 nums[i] 的和，最坏情况是 O(n²)。对 n 等于 10^5 的测试数据来说，O(n²) 也是超时级别的，跑不完。

还有人会想到建图 BFS：把每个位置当作节点，从 i 向 i+1 到 i+nums[i] 连边，然后从 0 开始 BFS。这个思路也不算错，但边的数量在最坏情况下同样是 O(n²)，空间复杂度随之上来了。如果你在面试现场只提出这个方案，面试官一般会追问一句：“能不能 O(n) 解决？”这句话就是在暗示你：这道题存在更简单的数学结构，不需要把可达性关系当作一张图来处理。

想明白暴力为什么不行之后，真正的突破口出现了：我们其实根本不需要关心“具体怎么跳”，只需要关心“最远能覆盖到哪里”。这就是贪心算法的入口。

2. 贪心解法的思考路径与代码实现

2.1 核心观察：可达区间是连续的

很多题解直接甩出“用一个变量记录最远可达下标，遍历一遍就完事”，但没有解释为什么这样是对的。我第一次看到这个解法时满脸问号：你怎么知道扫描到某个位置时，前面所有位置都一定可达？万一中间有一个不可达的点，但是最远可达点已经超过了它，那遍历还能继续吗？

答案在于：这道题的可达集合不是一个散乱的集合，而是一个从下标 0 开始的连续区间。

我来解释这个连续性的由来。假设当前我们已经枚举到了下标 i，并且 i 是可达的。从 i 出发，最多能跳 nums[i] 步，也就是说它可以到达 i+1、i+2、……、i+nums[i] 之间的任意一个位置。既然它可以跳到任意中间位置，那么[i+1, i+nums[i]]这一段就全部都是可达的，中间不会有空洞。

用这个逻辑往前推：一开始位置 0 可达，nums[0] 决定了[0, nums[0]]全可达；接着扫描到位置 1（前提是 1 在当前的覆盖范围内），它又把边界向右扩展到 1+nums[1]；再扫描位置 2，又把边界扩展到 2+nums[2]……这样一路扩展下去，被扫过的区域永远是连续的。

所以我们可以维护一个变量 farthest，表示当前已经能够到达的最远下标。只要当前扫描位置 i 没有超过 farthest，就说明 i 一定在可达区间内，我们可以放心地使用它的跳跃能力去继续扩展边界；一旦出现 i 大于 farthest 的情况，说明前面已经出现了“断层”，区间覆盖不到这里，后面也不可能跳过去，直接就可以判定无法到达终点。

这里有个容易绕进去的点：为什么维护一个 farthest 就够了，而不需要维护一个“当前区间内所有位置的跳跃能力集合”？因为我们只关心能不能到达终点，不关心最优路径。只要知道覆盖区间的右边界能推到多远，左边界永远是 0 且连续，这个问题就变成了一个纯粹的“边界推进”问题。这也是贪心能用的根本原因：全局最优结果完全由局部最大值决定，不需要回溯。

对照生活里的例子会更好理解。想象你在玩一个闯关游戏，角色站在 0 号踏板，每个踏板上的数字代表角色最多能向前弹出多远。只要前面还有足够长的踏板范围，角色每踩到一个新踏板，就可以用这个踏板的数字去“延长”自己当前能摸到的最大距离。你不需要设计每一步具体往哪跳，只需要不断问同一个问题：我现在最远能摸到哪里？如果某个踏板超出了我当前能摸到的最大距离，那这个踏板永远也踩不到，游戏必然失败。

2.2 代码实现与复杂度

理解了连续性之后，代码就非常自然了。Python 实现如下：

class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) farthest = 0 for i in range(n): if i > farthest: return False farthest = max(farthest, i + nums[i]) if farthest >= n - 1: return True return True

这里有几个细节需要说明。第一，循环范围是 range(n)，也就是会扫描到最后一个下标。当你站在最后一个下标时，已经满足“到达终点”的条件，所以会在循环内被提前返回。第二，判断 i > farthest 放在更新之前，是为了检测“当前位置已经不可达”的情况。第三，一旦 farthest >= n-1，说明终点已经在覆盖范围内，可以立刻结束，不用继续扫描。

Java 版本也顺手贴一下，方便面试时习惯用 Java 的朋友对照：

class Solution { public boolean canJump(int[] nums) { int n = nums.length; int farthest = 0; for (int i = 0; i < n; i++) { if (i > farthest) { return false; } farthest = Math.max(farthest, i + nums[i]); if (farthest >= n - 1) { return true; } } return true; } }

时间复杂度是 O(n)，因为每个位置只会被扫描一次；空间复杂度是 O(1)，只用了 farthest 这一个变量。这就是面试官想看到的终极形态：既没有辅助数组，也没有递归栈，纯粹靠状态感知完成全局判定。

还有一个常见写法是提前把 farthest 初始化为 nums[0]，然后从 i=1 开始循环。这样也能过，但边界条件容易写错：比如 n=1 时需要特判，或者循环范围要写成 range(1, n)。我个人的习惯是初始化为 0，从 i=0 开始统一处理，这样所有边界情况都自动包含在内，思维负担最小。

3. 同类型题的横向对比：DP方案与最少步数变体

3.1 动态规划能解吗：能，但没必要

很多人刷题时会形成一个惯性：看到“是否可达”就想动态规划。确实，跳跃游戏也可以用 DP 来做，定义 dp[i] 表示从起点能否到达下标 i。初始化 dp[0]=true，转移思路是：如果存在某个 j < i，使得 dp[j] 为真，并且 j + nums[j] >= i，那么 dp[i] 为真。

写成代码就是：

class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) dp = [False] * n dp[0] = True for i in range(1, n): for j in range(i): if dp[j] and j + nums[j] >= i: dp[i] = True break return dp[-1]

这个写法逻辑完全正确，但是有两层循环，时间复杂度 O(n²)，空间复杂度 O(n)。当 n 是 10^5 级别时，提交大概率超时。我当年为了验证自己“DP 也能做”，专门在本地生成了一个长度为 10^5 的随机数组，结果跑了将近两秒，而贪心解法连 1 毫秒都用不到。

为什么 DP 在这个问题上不是最优解？因为 DP 的状态保留了大量“中间可达性”信息，但这些信息对最终答案来说大部分是冗余的。我们需要的只是一个右边界，而 DP 却把每一个位置是否可达都记录了下来。换句话说，这道题的最优子结构太弱了，弱到不需要完整的子问题表，只需要一个不断向右推进的标尺。

我把三种思路放到一起对比，看得更清楚：

从复杂度上可以直观看出，同样是“正确解法”，贪心方案在工程意义上远远优于 DP 方案。如果你在面试中先给出 DP 方案，然后再说“但这题还能优化到 O(n)”，接着顺利写出贪心，面试官通常会很满意，因为这说明你有优化意识和复杂度敏感度。

3.2 跳跃游戏II：从“能否到”到“最少几步”

如果你把 55 题刷透了，我强烈建议紧接着就做跳跃游戏II，它几乎是同一套思维模型的自然延伸。跳跃游戏II 的问题变成了：假设你总能到达最后一个下标，求最少需要跳几次。

这个目标变化导致贪心策略也要升级。55 题只关心最远能覆盖到哪里，而 II 关心的是“覆盖到终点需要经历几个跳段”。核心思路是维护三个变量：当前跳段能达到的右边界 end、下一跳段能达到的最远距离 farthest、以及当前步数 step。

每遍历一个位置，就尝试更新 farthest = max(farthest, i + nums[i])。当遍历到 end 时，说明当前这一段已经走完了，必须跳一次，进入下一个覆盖区间，把 end 更新为 farthest，同时 step 加一。当 end 覆盖到 n-1 时，直接返回 step。

class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) end = 0 farthest = 0 step = 0 for i in range(n - 1): # 不需要扫描最后一个位置 farthest = max(farthest, i + nums[i]) if i == end: step += 1 end = farthest if end >= n - 1: return step return step

这个解法很巧妙地利用了“区间跳跃”的思想：每次跳跃不是从某个点跳到另一个点，而是从当前可达区间蹦到下一个更大的可达区间。你可以把它想象成把数组切分成若干个“跳段”，每个跳段覆盖一段连续的区间，段数就是最少跳跃次数。

回到 55 题本身，理解了这个变体之后，你会发现“能否到达”其实就是“最少步数是否存在”的一个退化版本。能到就是有解，不能到就是无解；跳跃游戏II 能 O(n) 求最少步数，也从侧面印证了 55 题的贪心正确性。

4. 实操中的坑、用例与面试追问

4.1 我在本地调试时反复踩过的写法错误

第一版代码我写的是 DFS，超时之后换成了贪心，本以为十行代码不会出错，结果本地跑还是遇到了几个隐蔽的边界坑，这里一个一个帮大家避掉。

第一个坑是循环边界。有人写了 for i in range(n-1)，意思是“最后一格不用扫”。但如果数组长度为 1，range(0) 直接不进入循环，最后 return True 倒是没问题；如果数组长度大于 1，而终点在第一步就能到达，比如 [5, 0, 0, 0, 0, 0]，你在 i=0 时就更新了 farthest 并立刻 return True，这也没问题。真正的问题出在有些写法把 return False 藏在循环外，一旦判断条件写松，很容易把终点也误判为不可达。稳妥做法是循环范围写 range(n)，让逻辑覆盖到所有下标。

第二个坑是“遇到 0 就以为死定了”。比如 [1, 0, 2] 这种用例，位置 1 是 0，看起来像死点，但实际上从 0 跳 1 步到位置 1 后会卡住；可是如果从 0 不跳到位置 1，而是直接……等等，nums[0]=1，只能跳 1 步，所以确实不能跳过位置 1。那换个例子 [2, 0, 0]，从 0 可以跳到 2，位置 1 的 0 不影响结果，返回 true。所以“0 不一定导致失败”，关键要看在扫描到该 0 位置之前，farthest 是否已经大于它。这个理解不到位，debug 时就会一脸懵。

第三个坑是把更新公式写错。有些人会写成 farthest = max(farthest, farthest + nums[i])，这看起来像是“用当前最远可达点继续跳”，但实际上完全错误。正确公式是 i + nums[i]，它表示从当前位置 i 出发能到达的最远点。你维护的变量已经是“所有已扫描位置的最远覆盖”，不是当前位置的父节点。这个错误很隐蔽，因为小规模数据可能碰巧能过，但一旦碰到需要跨越多个区间才能到达终点的用例就会翻车。

第四个坑是提前返回条件写成 farthest >= n 而不是 n-1。数组下标从 0 开始，终点是 n-1，所以覆盖到 n 其实已经超出范围了，逻辑上等价于覆盖到了 n-1，但会让代码看起来不严谨，面试时容易被追问。

第五个坑是忘记处理 n=1 的场景。当数组只有一个元素时，你站在起点就是终点，直接返回 true。上面的贪心代码天然支持这个情况：循环开始时 i=0，farthest >= n-1 变成 0>=0，直接 return True。但如果你把循环写成从 1 开始、farthest 初始化为 nums[0]，就要额外加一条 if n == 1: return True，多一个分支就多一个出错点。

4.2 建议自测的10组边界用例

我在本地刷题时习惯准备一组边界用例，每次改完代码都先跑一遍，能过滤掉百分之八十的低级错误。下面这组是针对跳跃游戏整理出来的，建议你也收藏一份：

重点留意最后这个 [4, 0, 0, 0, 0, 1]。从位置 0 出发最多跳 4 步，可以到 1、2、3、4，但他们全是 0；跳到 5 需要 5 步，超出 nums[0]=4 的能力范围，所以到不了位置 5 的 1。这个用例专门考验你是否有“覆盖区间可能被死点阻断”的意识。

跑这些用例的时候，我推荐你在关键分支处打印 farthest 和 i 的值，比如每遍历一个位置都输出 “i=2, farthest=3”。肉眼盯一轮输出，比单纯对着结果猜要容易定位问题得多。我记得有一次就是靠这个发现自己的更新公式写成了 farthest + nums[i]，在某个用例下 farthest 直接被顶到了 n，掩盖了真正的错误。

4.3 面试被追问时怎么答

面试官如果问你“为什么贪心是正确的”，不要只说“因为每一步都取最远可达”。你需要把连续性证明讲出来：从起点开始，维护的覆盖区间是连续的；扫描到区间内某个位置时，它的跳跃能力能把区间右端点继续向右延伸；只要区间右端点一直在更新，我们就不会遗漏任何可能的跳跃组合；如果某个位置超出区间，说明所有可能的跳跃组合都已经失败，不存在任何一条路径能到达那里。

这个逻辑链条里每一个环节都依赖“每次可以跳 0 到 nums[i] 之间任意步数”这个条件，这也就是为什么这题叫“最多可跳”而不是“必须跳这么多”。

还有一个高频追问是“如果题目改成输出一条可行路径怎么办”。贪心思路本身不保存路径，但你可以反向构造：从终点往前倒推，寻找能到达当前位置的最靠左的节点，然后继续往前倒退，最终得到一条路径。复杂度仍然是 O(n)，空间 O(n) 用来存路径。这个追问我遇到过一次，答完之后面试官很明显态度不一样，因为他知道我不只是背了题解。

还有更进一步的追问：“如果把 nums[i] 改成只能跳固定长度 nums[i]，这题怎么解？”那就变成了一个完全不同的判断问题，不能再用单纯的最远覆盖，因为可能跳过头，也可能无法精确踩中某些点，需要用更精细的状态记录取模等结构化信息。遇到这种扩展问题不用慌，冷静分析条件和原题的区别，把“连续可达”这个前提是否还成立想清楚就能给出合理的思路。

最后分享一个小技巧。刷这题的时候，我习惯把“farthest”理解成“当前角色的最大攻击范围”，而不是“已经走过的位置”。每踩到一个新格子，都会刷新一次攻击范围；只要攻击范围够到终点，游戏就赢了。这个心智模型帮我把很多跳跃类题目都统一起来了，包括跳跃游戏II、以及后来遇到的某些模拟跳跃题，都离不开“维护一个持续向终点推进的前沿”这个核心视角。希望这篇拆解也能帮你把 55 题彻底拿稳，而不是只记住那十行代码。