先问一个问题你第一次看到跳跃游戏这道题时第一反应是不是模拟跳一跳每步都试一遍我当初就是这么干的用递归回溯枚举所有跳跃路径结果一提交就超时。后来才想明白这题表面上是跳来跳去的动态过程本质上是一道区间覆盖问题。用贪心算法可以在时间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步落到下标3nums[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的134已经能直接覆盖终点。扫描过程中如果发现当前位置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问能不能到跳跃游戏IILeetCode 45则问最少跳几次到。题目保证一定能到终点所以只需要计算最小跳跃次数。先说直觉。假设你现在处于用k步能到达的最大范围内你在这些位置里挑选下一跳的起点。这时候你会选哪个起点当然是谁能让k1步的可达范围最远就选谁。注意这里不需要真的记录选了谁只需要记录我用k1步最远能覆盖到哪里。这个思路用变量currentEnd表示当前步数所能覆盖的边界用farthest表示扫描过程中发现的、下一步可以覆盖的最远位置。难点在于什么时候步数加一。我最初写这道题时总是在边界判断上出错后来总结出一个直观说法每当你扫描的位置越过了当前步数的右边界就说明不跳不行了必须花掉一步这一步能把你推到farthest记录的位置。3.2 currentEnd与farthest双边界是怎么配合的让我们用[2,3,1,1,4]手工跑一遍感受一下双边界的工作方式。初始steps 0currentEnd 0farthest 0。i 0farthest max(0, 02) 2。此时i currentEnd说明0步覆盖的边界到了必须跳一次steps 1currentEnd 2。i 1farthest max(2, 13) 4。i ! currentEnd不产生新跳跃。i 2farthest max(4, 21) 4。i currentEnd说明1步覆盖的边界到了必须再跳一次steps 2currentEnd 4。i 3farthest max(4, 31) 4。i ! currentEnd继续。循环结束steps 2。这个例子里farthest在i1时就达到了终点下标4但步数要等到i2越过currentEnd才增加。初学者常见的错误是看到farthest n-1就在i1时返回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返回truejump返回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]3maxReach3看起来能覆盖最后一位但如果数组是[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会输出i0: maxReach3i1: maxReachmax(3,2)3i2: maxReachmax(3,4)4i3: maxReachmax(4,3)4i4: maxReachmax(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只维护一个maxReachjump额外维护currentEnd和farthest都是常数个变量没有借用任何数组、哈希表或递归栈递归版本不算因为这里的贪心是迭代实现所以空间复杂度是O(1)。这也是题目所要求的最优解。5.4 和动态规划解法放在一起看动态规划也是解决这类问题的通用手段但代价高得多。对跳跃游戏IDP需要O(n)空间存储每个位置的可达性时间可能到O(n^2)跳跃游戏II如果用DP求最少步数同样需要O(n^2)时间和O(n)空间。相比之下贪心算法把两个指标都压到了极限。下面这张表可以帮你快速对比解法时间空间适用场景DFS回溯指数级O(n)递归栈数据量极小仅用于理解动态规划O(n^2)O(n)需要记录路径或扩展状态贪心本文O(n)O(1)只关心能否/最少步数不需要路径这也是面试官喜欢这道题的原因它会逼你在几分钟内判断出这题能不能用贪心而不是条件反射地套DP模板。6. 变体题目与面试延伸一招贪心能吃透多少题6.1 跳跃家族的其他成员贪心解决跳跃游戏的核心武器是维护可达区间边界这个思想能延伸到很多变体。比如跳跃游戏IIILeetCode 1306从任意起点出发可以向前或向后跳nums[i]步问能否到达值为0的位置。这题因为可以在区间内来回跳贪心失效需要BFS或DFS。跳跃游戏IVLeetCode 1345则给数组增加了一个规则值相同的下标之间可以跳转求从第一个下标到最后一个下标的最少步数常规思路是BFS再用哈希表合并相同值的节点来优化。还有一些虽然不是跳跃打头但底层逻辑相似。比如加油站问题LeetCode 134判断能否绕行一圈核心观察是总油量大于等于总消耗时答案一定存在并且可以从某个点贪心地找起点。这类问题的共同点非常明显要么是区间覆盖要么是全局可行性由某个守恒量决定。6.2 面试里怎么表达才能拿高分面试现场写出正确的贪心代码只是及格线。我建议的顺序是先说暴力回溯思路告诉面试官这是指数级不可取然后提出关键观察——可达位置是连续区间所以只需要维护右边界再给出O(n)/O(1)的贪心写法最后主动补充边界条件长度1、全0。这个递进能让面试官看到你的思考过程而不是背题。如果你上来就直接写一个maxReach面试官很难判断你是真懂还是记住了模板。有一个加分项主动说出为什么贪心是对的。你可以用归纳法证明连续性也可以说反例——每次跳最远不是最优。只要能证明maxReach的单调性面试官一般就放心了。我还会顺便提一句这题贪心成立是因为区间连续性不代表所有DP题都能贪心展现你的辨别能力。6.3 工程思维从跳跃问题到系统设计的联想跳出刷题跳跃游戏的贪心思路在工程里也有影子。比如CDN节点选择、链路路由跳数优化本质上都是在当前可达范围内寻找能延伸最远的下一跳跟跳跃游戏II的双边界逻辑惊人地相似。再比如资源分配问题里的区间调度要在一堆时间段里选出尽可能多的不重叠区间贪心策略是每次选最早结束的这个只维护当前最优边界的思路也是相通的。我后来做分布式系统里一步到位的故障恢复范围规划时也用过类似的区间覆盖思路。算法题到工程的距离往往比想象中近得多。最后再分享一个我个人的小习惯每次做完贪心题我都会问自己一句——这个贪心策略为什么不会被后效性影响跳跃游戏的答案是可达区间的连续性加油站问题的答案是总油量守恒。能回答上这个问题说明你真的吃透了题目而不是背了个模板。如果你刷题时也经常觉得自己看懂了但写不对不妨从这道题开始刻意练习这种先证明、后写码的习惯。