先问一个问题：你第一次看到跳跃游戏这道题时，第一反应是不是"模拟跳一跳，每步都试一遍"？我当初就是这么干的，用递归回溯枚举所有跳跃路径，结果一提交就超时。后来才想明白，这题表面上是"跳来跳去"的动态过程，本质上是一道区间覆盖问题。用贪心算法，可以在时间O(n)、空间O(1)的复杂度下拿到最优解，而且代码短到让人怀疑人生。

这篇文章我会从零拆解跳跃游戏的两个经典版本（LeetCode 55和45），把贪心思路的推导过程、正确性证明、边界条件和面试延伸一次讲透。无论你是刚开始刷算法题的新手，还是准备面试的老手，看完都能直接上手，不会再踩"差一步就能AC"的坑。

1. 题目拆解与直觉误区：跳跃游戏到底在考什么

1.1 问题回顾与三个错误直觉

先说题目本身：给定一个非负整数数组nums，你一开始站在下标0的位置，nums[i]表示你从位置i最多可以向后跳多远。问你能不能跳到最后一个下标。比如[2,3,1,1,4]，从0可以跳到1或2，实际存在路径0 -> 1 -> 4，答案是true；而[3,2,1,0,4]，无论怎么跳都会卡在下标3这个0上，答案是false。

这道题考察的绝不是"模拟跳跃"能力，而是对状态空间的理解。我刚学贪心算法时踩过三个典型误区，先说给你听，省得走弯路。

第一个误区：每次跳最远不就行了？初看很合理——跳得远选择多。但反例很容易构造，比如[3,1,2,0,1]。从0开始跳最远3步，落到下标3，nums[3]=0，直接卡死；可是如果先跳1步到下标1，再跳1步到下标2，然后从下标2跳2步到下标4，就成功了。所以"局部跳最远"不能保证全局最优，这个直觉必须丢掉。

第二个误区：用DFS/BFS暴力搜索。每到一个位置枚举所有可能的步数，看起来最"正确"，但状态数是指数级的。极端情况下，比如数组全是5，每个位置有5种跳法，暴力搜索的路径数量会急速膨胀，n稍微大一点就完蛋。更麻烦的是，同一位置会被重复访问很多次，大量重叠子问题被反复计算，白白浪费时间。

第三个误区：贪心不靠谱，老老实实写动态规划。跳跃游戏确实能用动态规划做，定义dp[i]表示位置i是否可达，然后对每个可达位置向前更新。但这样最坏情况是O(n^2)的时间复杂度。实际上这道题的决策结构比一般DP题简单得多，后面你会看到，只需要维护一个"最远可达位置"变量就足够了。

1.2 为什么"模拟跳跃"会卡死：状态空间的爆炸

想要明白贪心为什么能赢，先得知道暴力搜索输在哪。想象一下你从下标0出发，每一步的跳法是一个分支，所有可能的路径构成一棵树。最坏情况下，每个节点的孩子数量等于nums[i]，树的深度最多n层，路径数量就是阶乘级别甚至更高。哪怕用记忆化递归去剪枝，重复子问题依然很多，因为到达同一个位置的方式可能有好几种，而它们后续的决策完全一样。

我当年提交的第一版代码是这样的思路：boolean dfs(index)，如果index == n-1返回true，否则遍历1到nums[index]，递归调用dfs(index + step)。本地测试小样例全过，一到LeetCode的大数据就超时。后来我在纸上画了一下状态转移，发现这根本不是在解题，是在枚举所有人生。也是从那一刻起，我意识到跳跃游戏需要的不是"走一步看一步"的模拟，而是从更高维度去观察：既然跳过的中间位置一定会被经过，那问题就变成了"你能把可达区间扩展到多远"。

2. 贪心的核心：维护"最远可达位置"而不是"当前位置"

2.1 maxReach的定义：为什么是i + nums[i]

贪心解法的核心变量叫作maxReach，含义是：在当前已经扫描过的位置中，最远能够到达的下标。遍历到位置i时，更新方式是：

maxReach = max(maxReach, i + nums[i])

这里有个新手很容易忽略的细节：更新用的是i + nums[i]，而不是nums[i]。为什么？因为nums[i]是"从i出发还能走多远"，而我们要的是一个绝对下标。打个比方，nums[i]是你的余额，i是你当前的站点，i + nums[i]才是你刷这张卡最远能坐到哪一站。如果你只顾nums[i]，在[2,3,1,1,4]里，你计算出的最大"距离"是3，会误判为无法到达终点，但实际上下标1的1+3=4已经能直接覆盖终点。

扫描过程中，如果发现当前位置i已经超过了maxReach，说明前面的区间已经断掉了——没有任何已访问位置能延伸到这里，直接返回false。如果整个数组扫描完都没出现这种情况，说明可达区间始终连续扩张，而最后一个下标一定位于区间内，返回true。

2.2 可达区间的连续性：贪心正确性的命根子

很多人会问：凭什么只维护一个最大值就够了？万一中间有位置不可达，后面却又能到达怎么办？这个问题问得好，答案是：跳跃游戏的路径决定了可达位置一定是一段连续的区间。

你从下标0出发，不管怎么跳，每一步都会落到某个下标上。要到达位置k，你必然先经过一个更靠前的位置j，再从j跳到k。换句话说，如果你能到达k，那么0到k之间的所有整数位置，都能通过顺序经过到达。这个性质保证了"可达性"不会出现断层：只要当前扫描到的位置i还没超过maxReach，那么i就是可达的，并且从i还能继续向外扩展。

用归纳法证明很容易：初始时maxReach = 0，可达区间是[0, 0]。遍历到位置i时，因为i <= maxReach，所以i可达，从i出发最远能到i + nums[i]，于是区间扩张为[0, max(maxReach, i + nums[i])]。区间始终保持连续性。反过来，如果某个时刻i > maxReach，意味着0到i之间所有位置的可达性已经耗尽，区间出现缺口，后面不可能再连通，所以可以直接终止。

这个"连续区间"的视角，是理解整道题的关键。它把看似自由的跳跃问题，简化成了一个单调扩张的区间问题。很多资料直接甩代码，不讲这一层，导致读者背了模板却不会变通。

2.3 跳过终点的提前返回与代码细节

跳跃游戏I的参考实现如下：

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

这里有两个可以优化的小点。第一，maxReach >= n - 1时可以直接返回true，因为终点已经在可达区间内，没必要继续扫。第二，很多人喜欢把循环写成range(n)，也有人写成range(n - 1)。写range(n)最保险，逻辑最直白；写range(n - 1)也能过，因为终点位置本身的跳跃能力不影响"能否到达它"的判断，但前提是你前面的i > maxReach判断逻辑要正确。我个人的建议是：用range(n)，少一点心智负担。

提示：这题的贪心思路总结成一句话就是"扫描所有位置，维护最大覆盖右边界，发现扫描位置超出右边界就判定失败"。记住这句话，跳跃游戏I你永远不会忘。

3. 从"能不能到"到"最少几步"：跳跃游戏II的双边界贪心

3.1 题目差异与"必须跳一次"的直觉

如果跳跃游戏I问"能不能到"，跳跃游戏II（LeetCode 45）则问"最少跳几次到"。题目保证一定能到终点，所以只需要计算最小跳跃次数。

先说直觉。假设你现在处于"用k步能到达的最大范围"内，你在这些位置里挑选下一跳的起点。这时候你会选哪个起点？当然是谁能让"k+1步的可达范围"最远，就选谁。注意，这里不需要真的记录选了谁，只需要记录"我用k+1步最远能覆盖到哪里"。这个思路用变量currentEnd表示当前步数所能覆盖的边界，用farthest表示扫描过程中发现的、下一步可以覆盖的最远位置。

难点在于"什么时候步数加一"。我最初写这道题时总是在边界判断上出错，后来总结出一个直观说法：每当你扫描的位置越过了当前步数的右边界，就说明不跳不行了，必须花掉一步，这一步能把你推到farthest记录的位置。

3.2 currentEnd与farthest：双边界是怎么配合的

让我们用[2,3,1,1,4]手工跑一遍，感受一下双边界的工作方式。初始steps = 0，currentEnd = 0，farthest = 0。

• i = 0：farthest = max(0, 0+2) = 2。此时i == currentEnd，说明0步覆盖的边界到了，必须跳一次，steps = 1，currentEnd = 2。
• i = 1：farthest = max(2, 1+3) = 4。i != currentEnd，不产生新跳跃。
• i = 2：farthest = max(4, 2+1) = 4。i == currentEnd，说明1步覆盖的边界到了，必须再跳一次，steps = 2，currentEnd = 4。
• i = 3：farthest = max(4, 3+1) = 4。i != currentEnd，继续。
• 循环结束，steps = 2。

这个例子里，farthest在i=1时就达到了终点下标4，但步数要等到i=2越过currentEnd才增加。初学者常见的错误是看到farthest >= n-1就在i=1时返回1，那就是错的——你还没有实际跳那一步呢。farthest是"下一跳的潜力"，不是"已经消耗的步数"。

3.3 为什么循环只到n-1或n-2：最后一步不用真的跳

跳跃游戏II的标准写法是遍历到n-1还是n-2？很多答案不一致，其实关键在于你处理边界的方式。上面手工推导用的写法是这样的：

def jump(nums): n = len(nums) if n <= 1: return 0 steps = 0 currentEnd = 0 farthest = 0 for i in range(n - 1): farthest = max(farthest, i + nums[i]) if i == currentEnd: steps += 1 currentEnd = farthest if currentEnd >= n - 1: break return steps

遍历到n-1是因为：我们关心的是处于"还没到达终点"的位置时如何扩张范围，而最后一个位置已经是终点了，不需要再从它出发跳一次。假如遍历到n-1，在某些写法里会在终点处又触发一次i == currentEnd，导致步数多算。所以稳妥做法是只遍历到n-2，并且在步数增加后立即判断是否已到达终点，能提前break就提前break。

注意：jump函数里的提前break和canJump里的提前return一样，都是小优化。真正写对的关键是"步数增加发生越过右边界时，而不是发现潜力时"。

4. 边界条件与常见陷阱：为什么你的代码差一点就过

4.1 数组长度为1：最简单也最容易被测试卡到

如果nums = [0]，你已经在终点，canJump返回true，jump返回0。这个边界条件应该单独判断，否则你的currentEnd初始化为0，进入循环后可能把steps算成1，直接错误。千万别觉得这是小事，很多面试者在这种用例上翻车。

4.2 全0数组与"断点"位置的判断

全0数组能不能到达终点？除了[0]这种长度1的情况，其他全0数组答案都是false，因为第一步就卡死。比如[0, 1, 2]，从0出发跳0步，根本无法离开第一个位置。这里隐藏着一个更普遍的判断方法：只要扫描过程中出现i > maxReach，就说明存在一个"断点"，后面无论元素多大都白搭，因为到达不了那个位置。所以canJump只要有这一个判断就够了。

4.3 最后一个位置到底要不要遍历：两种写法的取舍

跳跃游戏I的标准写法遍历全数组，包括最后一个位置。你可能觉得奇怪：最后一个位置还需要判断i > maxReach吗？其实当循环跑到n-1时，如果maxReach还没覆盖到n-1，会返回false；覆盖到了，循环自然结束返回true。所以遍历到n-1是安全的。也可以只遍历到n-2，最后直接判断maxReach >= n - 1。两种写法都正确，但我的经验是：如果你在面试中紧张，就写遍历全数组的版本，逻辑最简单，不容易写错。

跳跃游戏II则不同，循环范围是range(n - 1)，因为最后一个位置不需要作为"出发点"。这个差异常常让刷题新手困惑，建议把两题的循环范围当成两个固定模板来记，而不是强行统一。

4.4 最容易摔跤的地方：漏掉i + nums[i]里的i

我在给同事review代码时，发现十个写跳跃游戏的人，至少有三个把更新写成maxReach = max(maxReach, nums[i])。这种写法在[3,0,0,0]这种例子上就会误判：nums[0]=3，maxReach=3，看起来能覆盖最后一位，但如果数组是[1,0,3]，只用nums[i]会得到最大值3，误判为true，而实际从0只能到1，卡死在1。所以每次写这题时，我都要在脑子里过一遍：先加下标，再取max。

我还见过有人在跳跃游戏II的循环里把i + nums[i]和currentEnd、farthest搞混，把farthest初始化为nums[0]而不是0。这种做法在nums[0]=0时会直接出错。记住，farthest应当是"扫描过程中看见的最远潜力"，只有遍历到了才会更新。

4.5 调试技巧：打印可达区间一眼看出问题

如果你写完代码还是不对，试试在循环里打印每个i对应的maxReach或farthest。以[3,1,2,0,1]为例，canJump会输出：

• i=0: maxReach=3
• i=1: maxReach=max(3,2)=3
• i=2: maxReach=max(3,4)=4
• i=3: maxReach=max(4,3)=4
• i=4: maxReach=max(4,5)=5

看到区间[0, 5]连续扩张，算法就正确。如果打印出来发现某个i的maxReach小于i，那你就能定位到具体的断点，排查是更新公式写错了，还是比较条件写反了。这个调试方法对我特别管用，比盯着代码干想快得多。

5. 复杂度下界与最优性论证：为什么时间O(n)空间O(1)就是天花板

5.1 时间O(n)：一趟扫描解决一切

两个版本的贪心算法都只遍历一次数组，循环体里是常数次比较和赋值操作，因此时间复杂度是严格的O(n)。这两个算法不需要排序，不需要二分，不需要预处理，纯粹靠一趟从左到右的扫描就完成了计算。

5.2 为什么不可能低于O(n)：信息论的下界直觉

你可能想问：这个算法是不是还能更快？答案是否定的。任何正确的算法在最坏情况下都至少要检查每个元素一次。理由很直观：数组里任意一个元素都可能成为"关键的跳板"或者"卡死整个路径的断点"。如果你完全忽略某个位置k的值，那我们就可以构造两个数组——除了位置k的值不同，其他完全相同。一个数组里nums[k]=0导致路径断裂，另一个数组里nums[k]非常大使路径连通。忽略k的算法无法区分这两个输入，必然有一个会判错。所以O(n)是算法复杂度的时间下界，这题没有更快的可能。

5.3 空间O(1)：只用了两个整数变量

空间上，canJump只维护一个maxReach，jump额外维护currentEnd和farthest，都是常数个变量，没有借用任何数组、哈希表或递归栈（递归版本不算，因为这里的贪心是迭代实现），所以空间复杂度是O(1)。这也是题目所要求的最优解。

5.4 和动态规划解法放在一起看

动态规划也是解决这类问题的通用手段，但代价高得多。对跳跃游戏I，DP需要O(n)空间存储每个位置的可达性，时间可能到O(n^2)；跳跃游戏II如果用DP求最少步数，同样需要O(n^2)时间和O(n)空间。相比之下，贪心算法把两个指标都压到了极限。下面这张表可以帮你快速对比：

这也是面试官喜欢这道题的原因：它会逼你在几分钟内判断出"这题能不能用贪心"，而不是条件反射地套DP模板。

6. 变体题目与面试延伸：一招贪心能吃透多少题

6.1 跳跃家族的其他成员

贪心解决跳跃游戏的核心武器是"维护可达区间边界"，这个思想能延伸到很多变体。比如跳跃游戏III（LeetCode 1306），从任意起点出发，可以向前或向后跳nums[i]步，问能否到达值为0的位置。这题因为可以在区间内来回跳，贪心失效，需要BFS或DFS。跳跃游戏IV（LeetCode 1345）则给数组增加了一个规则：值相同的下标之间可以跳转，求从第一个下标到最后一个下标的最少步数，常规思路是BFS，再用哈希表合并相同值的节点来优化。

还有一些虽然不是"跳跃"打头，但底层逻辑相似。比如加油站问题（LeetCode 134），判断能否绕行一圈，核心观察是"总油量大于等于总消耗"时，答案一定存在，并且可以从某个点贪心地找起点。这类问题的共同点非常明显：要么是区间覆盖，要么是"全局可行性由某个守恒量决定"。

6.2 面试里怎么表达才能拿高分

面试现场写出正确的贪心代码只是及格线。我建议的顺序是：先说暴力回溯思路，告诉面试官这是指数级，不可取；然后提出关键观察——可达位置是连续区间，所以只需要维护右边界；再给出O(n)/O(1)的贪心写法；最后主动补充边界条件（长度1、全0）。这个递进能让面试官看到你的思考过程，而不是背题。如果你上来就直接写一个maxReach，面试官很难判断你是真懂还是记住了模板。

有一个加分项：主动说出"为什么贪心是对的"。你可以用归纳法证明连续性，也可以说反例——每次跳最远不是最优。只要能证明maxReach的单调性，面试官一般就放心了。我还会顺便提一句"这题贪心成立是因为区间连续性，不代表所有DP题都能贪心"，展现你的辨别能力。

6.3 工程思维：从跳跃问题到系统设计的联想

跳出刷题，跳跃游戏的贪心思路在工程里也有影子。比如CDN节点选择、链路路由跳数优化，本质上都是在"当前可达范围内寻找能延伸最远的下一跳"，跟跳跃游戏II的双边界逻辑惊人地相似。再比如资源分配问题里的"区间调度"，要在一堆时间段里选出尽可能多的不重叠区间，贪心策略是每次选最早结束的，这个"只维护当前最优边界"的思路也是相通的。我后来做分布式系统里一步到位的故障恢复范围规划时，也用过类似的区间覆盖思路。算法题到工程的距离，往往比想象中近得多。

最后再分享一个我个人的小习惯：每次做完贪心题，我都会问自己一句——"这个贪心策略为什么不会被后效性影响？"跳跃游戏的答案是"可达区间的连续性"，加油站问题的答案是"总油量守恒"。能回答上这个问题，说明你真的吃透了题目，而不是背了个模板。如果你刷题时也经常觉得自己"看懂了但写不对"，不妨从这道题开始，刻意练习这种"先证明、后写码"的习惯。