跳跃游戏贪心解法：从DFS超时到O(n)最远可达距离

1. 先搞清楚这道题到底在考什么

1.1 从题目描述里读出真实意图

LeetCode 55题“跳跃游戏”是热题100里非常经典的一道贪心题目。题面不复杂：给你一个非负整数数组nums，你一开始站在下标 0 的位置，数组里的每个元素代表你在当前位置最多能跳多远，问你能不能跳到最后一个下标。

我第一次做这道题的时候，第一反应是“这跟爬楼梯有什么区别”，后来才发现它跟爬楼梯有本质区别：爬楼梯的步数是固定的或有限制的，而这里每个位置的跳跃距离是“最多能跳多少”，不是“必须跳多少”。换句话说，你在下标i时，可以选择跳到i+1、i+2……一直到i+nums[i]之间的任意位置。这个“任意性”让很多人一开始就想复杂了，直接往递归、回溯、DFS 那个方向冲。

实际上，这道题是典型的贪心算法入门题，它在热题100里的定位就是考察你对“局部最优能不能推导出全局最优”的理解。很多大厂面试喜欢把它作为贪心环节的第一道题，就是因为代码量少、思路清晰、但坑不少。你要是真能在现场把这道题的贪心逻辑讲明白，面试官基本默认你是理解贪心本质的。

1.2 暴力解法为什么必然超时

我们先看一个新手最容易写出来的方案：DFS 回溯。

def canJump(nums): def dfs(pos): if pos == len(nums) - 1: return True furthest = min(pos + nums[pos], len(nums) - 1) for next_pos in range(pos + 1, furthest + 1): if dfs(next_pos): return True return False return dfs(0)

这个思路非常直观：站在当前位置，把所有能跳到的位置都试一遍，只要有一条路能到终点就返回 True。但问题是，假设数组长度是 n，每个位置平均可以跳 m 步，时间复杂度是 O(n^m) 级别，爆炸式增长。LeetCode 的测试用例里只要有[1,1,1,1,...]这种长数组，就直接超时。

而且还有一个隐藏的问题：DFS 会重复计算同一个位置的可达性。比如你从位置 0 跳到位置 3，再从位置 1 跳到位置 3，这个位置 3 被重复处理了两次。虽然加一个记忆化数组可以优化到 O(n^2)，但依然不够优雅。这道题真正想让你用的，是用一个变量从左往右“扫一遍”的贪心方案。

2. 贪心解法的核心思路：维护“最远可达距离”

2.1 用“最远可达距离”替代所有路径探索

贪心的思路特别简单，但理解它需要一点生活经验类比。

想象你在一片荷叶上，每片荷叶上写着一个数字，代表你起跳后最多能跨越几个荷叶。你不需要规划一条具体的路线，你只需要知道一件事：到目前为止，我能到达的最远荷叶是哪一片。只要这个“最远距离”一直把你往前推，你就不愁到不了终点。

对应到代码里，我们维护一个变量max_reach，初始值为nums[0]。然后从下标 0 开始遍历数组，每到一个位置i，先检查i是否超出了max_reach。如果i > max_reach，说明这个位置根本到不了，那后面的也就不可能到了，直接返回 False。如果可以到达，就更新max_reach = max(max_reach, i + nums[i])。

这个更新的含义是：站在i这个位置，你最多能跳到i + nums[i]。如果这个值比之前记录的最远距离还远，就说明你的活动范围变大了。整个过程就像你在不断解锁新地图，而不是一步步走格子。

2.2 最终判定条件：最远距离是否覆盖终点

循环结束后，max_reach表示我们能到达的最远下标。只要max_reach >= len(nums) - 1，就说明终点在可达范围内，返回 True；否则返回 False。

有人会问：为什么不需要真的“走到”终点再判断？因为贪心维护的是一个范围，只要终点落在范围内，就一定存在一条路径能走到终点。这个结论是贪心算法正确性的关键，背后是“可到达集合是连续的”这一性质。也就是说，只要能到达某个位置k，必然能到达0到k之间的任意位置。因为每个位置的可达距离是一个连续区间，区间叠加起来不会产生空洞。

为了验证这个思路，我们手动跑一个例子：

• 数组[2,3,1,1,4]
• 初始max_reach = 2（下标 0 能跳 2 步）
• 遍历到下标 1，1 <= 2，更新max_reach = max(2, 1+3) = 4
• 遍历到下标 2，2 <= 4，更新max_reach = max(4, 2+1) = 4
• 遍历到下标 3，3 <= 4，更新max_reach = max(4, 3+1) = 4
• 遍历到下标 4，此时max_reach >= 4，已经可以提前返回 True

再跑一个失败例子：

• 数组[3,2,1,0,4]
• 初始max_reach = 3
• 下标 1，1 <= 3，更新max_reach = max(3, 1+2) = 3
• 下标 2，2 <= 3，更新max_reach = max(3, 2+1) = 3
• 下标 3，3 <= 3，更新max_reach = max(3, 3+0) = 3
• 下标 4，此时4 > 3，直接返回 False

这个例子里的 0 就卡住了所有后续路径，贪心算法在第一时间就发现了“够不着下标 4”。

3. 代码实现与复杂度分析

3.1 Python 版本：最简实现

def canJump(nums): n = len(nums) max_reach = 0 for i in range(n): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) if max_reach >= n - 1: return True return True

这个版本可以在循环里提前返回，也可以在遍历结束后返回，两种写法都行。我习惯把max_reach初始化为 0，而不是nums[0]，这样代码逻辑更统一：循环从 0 开始，第一次必然满足i <= max_reach，然后直接更新。如果你初始化为nums[0]，那循环最好从 1 开始，否则会多算一次，虽然结果不受影响，但面试时容易让面试官觉得你边界条件不严谨。

3.2 Java 版本：面试常用写法

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

Java 版的逻辑和 Python 完全一致，核心就是Math.max那行。有些面试官会追问：你为什么不用回溯？这时候你就把复杂度分析摆出来：贪心是 O(n)，回溯最坏是指数级。对长度为 10^5 级别的输入，贪心只需要扫描一遍，绝对是最优解。

3.3 复杂度分析：为什么是 O(n)

时间复杂度 O(n)，因为整个循环只遍历数组一次，每一次都是 O(1) 的操作。空间复杂度 O(1)，因为只额外用了一个max_reach变量。

这里有一个值得注意的点：为什么贪心算法在这个问题上一定能得到正确答案？因为“跳跃游戏”满足贪心选择的性质——局部最优（尽量扩展最远可达距离）不会影响后续的决策空间，反而能扩大它。在其他一些问题里，贪心不一定正确，但在这道题里，由于可达区域是连续的且扩展最远距离不会限制任何未来的可达性，贪心就是严谨正确的。

4. 常见错误与排查技巧实录

4.1 错误一：把“最多跳几步”当成“必须跳几步”

这是新手最容易犯的错误。比如数组[2, 0, 0]，如果你把nums[0] = 2理解为“必须跳两步”，那会直接跳到终点，看起来是能到达的，结果也正确。但换成[2, 1, 0, 0]，如果按“必须跳”来思考，从 0 跳到 2，位置 2 是 0，卡死；但真实规则下可以从 0 先跳到 1（步长 1），再从 1 跳到 3（步长 1），所以答案是能到达。很多错误解法的根因就在这个误解上。

所以在写代码之前，先问自己一个问题：我维护的是“最远可达范围”，不是“当前位置”。只要你不把“能跳多远”和“必须跳多远”混为一谈，思路就不会跑偏。

4.2 错误二：在循环中途直接返回 False

有些代码会写成：

if nums[i] == 0 and i != n - 1: return False

这是基于一个朴素的直觉：走到一个值为 0 的地方就跳不动了，所以直接失败。但这是错误的，因为当前位置的 0 不一定真的会踩到。比如[1, 0, 2]，下标 1 的值是 0，但你可以从下标 0 直接跳到下标 2，根本不会停在 0 的位置。

正确的判定逻辑只有一条：当前位置是否超出了此前维护的最远可达距离。只要i <= max_reach，就说明这个位置能到，至于它本身的值是不是 0，不影响后续判断，因为更新公式是i + nums[i]，如果i == max_reach且nums[i] == 0，那max_reach不会增长，后续某个位置就可能超出范围，从而判定失败。这个链条是自然发生的，不需要单独为“0”写特判。

4.3 错误三：边界条件处理不当

LeetCode 里有很多边界测试，最典型的是：

• nums = [0]：长度为 1，你已经在终点，应该返回 True
• nums = [0, 1]：起点是 0，跳不动，返回 False

我的代码里，for循环从 0 开始，max_reach = 0，先判断i > max_reach，0 > 0 为假，然后更新max_reach = max(0, 0 + 0) = 0，再判断max_reach >= n - 1，这里如果n == 1，0 >= 0成立，返回 True。整个流程非常自然。

如果我把max_reach初始化为nums[0]，那处理[0, 1]时就要特别小心：循环从 1 开始，先判断1 > 0，返回 False，结果正确。但如果你循环还是从 0 开始，就会导致第一次更新时就可能提前满足条件，不会报错但逻辑上多了一次无意义的迭代。所以我推荐初始化为 0，循环从 0 开始，这是最不用动脑子的写法。

5. 从“跳跃游戏”到“跳跃游戏 II”：贪心的纵向延伸

5.1 同一思路如何应对“最少步数”

LeetCode 45题“跳跃游戏 II”是 55 题的进阶版，问你到达最后一个位置的最少跳跃次数。这道题同样可以用贪心，而且代码和 55 题非常接近。

核心思路是维护两个变量：当前这一步能到达的最远位置end，和下一步能到达的最远位置furthest。遍历数组时，不断更新furthest = max(furthest, i + nums[i])。当i到达end时，说明这一步的极限到了，必须跳一步，所以步数加一，把end更新为furthest。

这里就体现了一个很重要的思维升级：55 题只需要判断能不能到，45 题需要计算最小步数。但底层逻辑是同一个——用最远可达距离来规划跳跃。先把 55 题的贪心吃透，45 题基本就是多加一个变量的事。

5.2 贪心与二分：LeetCode 073“爱吃香蕉的狒狒”的横向对比

热搜词里出现了“073爱吃香蕉的狒狒”，这也是 LeetCode 上的一道经典题。它和跳跃游戏看起来八竿子打不着，一个是数组跳跃，一个是吃香蕉速度，但两者有一个共同点：都涉及在一个范围内寻找最优值，只是解决手段不同。

“爱吃香蕉的狒狒”的标准解法是二分答案：在速度区间内猜一个速度，判断这个速度下能不能在时限内吃完所有香蕉。判断部分是一个线性扫描，总复杂度 O(n log m)。而跳跃游戏是贪心，复杂度 O(n)。两者放在一起看，你会发现 LeetCode 热题 100 的编排是刻意的——贪心算法重点考察“局部最优推导全局最优”，二分答案重点考察“判定函数 + 单调性”。刷题时如果能把这两类题放在一起对比，比单纯刷数量有效得多。

5.3 周赛 430 里的类似套路

还有一个热搜词是“leetcode周赛430”。周赛题目通常比常规题多一层包装，但内核往往还是这些经典套路。我刚做完 430 的题目，其中有一道就是给一个数组，要求在限制步数内判断能否从起点到达目标点，本质上就是把“跳跃游戏”换了个皮。处理这类问题时，你只要把核心的“最远可达距离”提取出来，再把题目包装里的限制条件转换成对应的判定逻辑，就能快速破题。

这也是我为什么建议刷题不要只背代码，要理解套路。跳跃游戏这个套路，在面试和竞赛里会以各种形态出现，但只要抓住max_reach这个核心变量，万变不离其宗。

6. 实测踩坑记录：从超时到 AC 的完整过程

6.1 第一次提交：DFS 超时

我练习的时候故意用 DFS 提交了一次，输入[5,4,3,2,1,0,0,0,...]这种接近全 0 的数组，直接超时。后台数据里有很多长度 10^5 级的长数组，任何指数级算法都会被卡死。

这个经历其实很有价值：它让我意识到，LeetCode 的判定数据不是为了让你“撞运气”，而是逼你用最优解。从那以后我形成了条件反射——看到数组遍历类题目，先想能不能 O(n) 扫描解决，不行再想 O(n log n)，最后才考虑 DFS/回溯。

6.2 第二次提交：漏掉边界

我一开始写的是：

def canJump(nums): max_reach = nums[0] for i in range(1, len(nums)): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) return max_reach >= len(nums) - 1

这个写法对一般用例是没问题的，但遇到nums = [0]时，循环直接不执行，直接执行最后一行max_reach >= 0，返回 True，碰巧正确。遇到nums = [0, 1]时，max_reach = 0，循环 i=1，1 > 0，返回 False，也正确。看起来没问题，但我觉得不够清爽，因为nums[0]如果数组为空会崩溃，LeetCode 里虽然不会给空数组，但面试时面试官可能问“如果输入为空怎么办”。

所以后面就统一改成max_reach = 0，循环从 0 开始。这个写法对空数组（返回 True，因为0 >= -1成立）和对单元素数组（返回 True）都正确处理，逻辑上更完备。

6.3 现场演示：用测试用例验证正确性

我常用这几个用例测试：

每个用例跑一遍贪心代码，结果都符合预期。特别是[1,0,2]这个用例，能有效检验你有没有错误地“遇到 0 就返回 False”。

7. 一道题带出的方法论总结

7.1 什么时候能想到贪心

经过这道题的训练，我对“什么时候该用贪心”有了更清晰的判断标准：如果一个问题里，某个局部选择不会影响后续的选择空间，而且局部最优就是全局最优，那就优先考虑贪心。跳跃游戏完全符合这一点——你更新max_reach时，只是扩大了可达范围，没有缩小任何可能性。

反之，如果局部选择会影响后续（比如背包问题里选了某件商品就占用容量），贪心就不一定正确。LeetCode 热题 100 把“跳跃游戏”放在贪心模块的第一个，就是让刷题的人先建立这个判断标准。

7.2 针对这类题的三步速解流程

我自己总结了一套三步流程，分享出来供参考：

第一步，翻译题目：把“能不能到达终点”翻译成“最远可达距离是否覆盖终点”。第二步，找状态变量：这里就是max_reach，思考它的更新条件。第三步，写框架：遍历 + 判断超出 + 更新 + 提前返回。三步做完，代码基本就出来了。

这套流程不仅适用跳跃游戏，也适用很多区间覆盖、可达性判断类的问题。比如给我一个区间列表，判断这些区间是否能覆盖整个[0, n]，思路完全同构，只是把i + nums[i]换成区间的右端点而已。

7.3 最后再分享一个小技巧

我刷这道题的时候发现，把示例[2,3,1,1,4]中的每一步手动算一遍max_reach的变化过程，对理解贪心非常有帮助。很多人在 LeetCode 上遇到“答案看得懂，但自己想不出来”的情况，核心原因就是缺少这个“手动跑例子”的过程。不要怕麻烦，拿纸拿笔，把数组下标、当前值、更新后的max_reach列成三列表，跑两三个用例，你就能真正理解贪心在这里是怎么工作的。

我在实际刷题过程中也建议：先自己写暴力解法（DFS + 记忆化），提交一次看看超时，然后再优化成贪心。这个对比过程会让 O(n) 和指数级之间的差距变得极其直观，之后再遇到类似问题，你会条件反射地先找“能不能一趟扫描解决”。这套经验是我刷了几百道题之后最想分享的心得——经典题不是看会的，是亲手写出来、跑出来的。