一直被“到达不了终点”折磨的人看完这篇应该能少走很多弯路。力扣 Hot 100 的第 55 题“跳跃游戏”是所有刷题人都绕不过去的一道经典题。它的题干很短给你一个非负整数数组初始位置在下标 0每个元素代表你在该位置最多能向前跳的步数判断你能不能跳到最后一个下标。看似简单但它背后的贪心思想、边界判断和变体展开几乎涵盖了一大类“区间可达性”问题的核心框架。这篇文章我会把题目怎么读、思路怎么来、代码怎么写、踩坑怎么避以及它和后续题目的关系全部拆开讲清楚希望能帮你一次吃透。本人刷题有个习惯同类题型至少横向对比三到五道再总结出一套自己的判断逻辑。这道题我在两个不同阶段写过完全不一样的解法第一版甚至用上了带记忆化的回溯结果代码又臭又长。后来重新推导才发现贪心一行核心判断就能解决。前后对比我觉得最有价值的部分不是答案本身而是“如何从暴力思路一步步收敛到最优解”的思考过程。这篇文章会按照这个思路来展开无论你是刚开始刷 Hot 100还是刷到一半卡在这里应该都能从中获得一点启发。1. 题目理解与核心思路拆解1.1 题目到底在说什么先原封不动把题面核心信息摆出来给定一个非负整数数组nums你初始位于数组的第一个下标nums[0]。数组中的每个元素代表你在该位置可以跳跃的最大长度——注意关键词是“最大”不是“必须”。也就是说如果当前位置的值是 3你可以选择跳 1 步、2 步或者 3 步。目标是从下标 0 走到最后一个下标判断是否可行。举个例子nums [2, 3, 1, 1, 4]从下标 0 出发nums[0] 2最远能到下标 2。你可以先跳到下标 1发现nums[1] 3又能往前覆盖到下标 4所以答案返回 true。再比如nums [3, 2, 1, 0, 4]从下标 0 出发最远能到下标 3但是下标 3 的值是 0一步都动不了无法越过这个位置到达下标 4所以答案是 false。很多新手读题时会犯一个先入为主的错误把“最大跳跃长度”理解成“只能跳最大长度”。一旦这么理解第二道示例直接变成“从 0 跳到 3然后卡死”甚至会得出“必须路径可行才叫可行”的错觉。做题之前先把这个概念厘清后面的代码才不会写偏。1.2 为什么暴力回溯走不通最直观的解法是暴力回溯从下标 0 出发枚举每一步可以跳到的所有位置递归地尝试每一种跳法。如果某条路径能到达终点就直接返回 true否则尝试下一条。这种解法和“走迷宫”的思路几乎一样简洁且容易理解。但暴力回溯的复杂度是指数级的。假设每一步平均有 k 种跳法路径深度是 n那么最坏情况下要尝试 k 的 n 次方量级的组合。nums长度稍微大一点比如 100程序几乎就卡死了。我在第一次做这道题时先用回溯写完本地测试小数组没问题一提交就超时。后来我补了一个memo数组记录“某个下标是否已经被计算过不可达”复杂度才降到 O(n²)勉强能跑。这个优化版本其实已经是“动态规划记忆化搜索”的雏形了。回溯的问题在于它没有利用“已经探索过的位置”的信息。同一个下标可能被不同路径重复访问而每次访问都会重新递归一遍。记忆化可以缓解一部分重复计算但它仍然不是最优解。这道题真正的转折点是意识到我们根本不需要记录“具体走哪条路”只需要关心“当前能触及的最远边界在哪里”。1.3 从动态规划视角看这个问题如果你脑子里装着“最优化”三个字很容易想到动态规划。设dp[i]表示从下标 0 出发能否到达下标 i那么dp[i]可以由所有能跳到 i 的位置 j 转移而来只要存在某个 j 满足dp[j] true且nums[j] i - jdp[i]就为 true。这个转移方程是正确的时间复杂度 O(n²)空间复杂度 O(n)。在面试或者刷题阶段如果只求 ACO(n²) 也能通过不少测试用例。但 Hot 100 里的题目考察的往往是更进一步的优化能力。仔细观察会发现dp[i]的转移依赖的不是某个具体的前驱状态而是一个“区间范围”——所有能到达的位置会形成一个连续的前缀区间。一旦你读出了这个特征贪心解法就是水到渠成的事情。我还见过用 BFS 解法的同学把每个位置能跳到的所有位置看作邻接节点从起点开始层序遍历看能否遍历到终点。正确性没问题但建图的时间和空间开销都不小而且完全没有利用“跳跃范围连续”这个性质。这道题如果真的按图来处理属于典型的杀鸡用牛刀能锻炼思维但绝不是最优答案。2. 贪心算法的核心细节与推导2.1 维护最远可达距离先说结论遍历数组实时维护一个变量maxReach表示“当前能够到达的最远下标”。遍历到下标 i 时如果i maxReach说明这个位置根本走不到直接返回 false否则用nums[i] i更新maxReach取最大值。一旦maxReach n - 1说明终点已经可达返回 true。这句话听起来非常简单但它背后有三个关键点值得细想。第一为什么只需要记录最远距离而不关心“中间到底能不能到达”因为跳跃的步长是连续的如果某个位置 i 可达那么从起点到 i 的路径上所有下标都必然可达。这个性质用反证法可以证明如果路径上某个中间位置 k 不可达那么这条“经过 k 到达 i”的路径就不可能成立。所以可达位置集合永远是[0, maxReach]这段连续区间维护区间右端点就够了。第二更新时机问题。我们是在遍历到某个下标时才更新maxReach而不是在一开始就一次性算出全局最远。这背后的逻辑是只有“已经可达”的区域内的位置它提供的跳跃能力才是有效的。如果某个位置本身不可达就算它的nums[i]再大也无法帮助我们前进。这个“跟随遍历逐步扩张可达边界”的思路是贪心算法里很典型的模式。第三终止条件的把握。循环可以有两种写法一种是遍历所有下标直到 n-1另一种是每轮更新后立刻判断maxReach n - 1提前返回。两种写法结果一样但提前返回的版本在“终点很快就可达”的用例里能省掉不少无谓迭代尤其在数组特别长时收益明显。2.2 为什么贪心在这里是对的很多人一听到贪心第一反应是“局部最优不一定等于全局最优”然后开始怀疑只是每次都取最远跳跃真的能保证找到一条到达终点的路径吗这个怀疑是合理的但这道题恰好满足贪心选择性质。关键在于我们维护的“最远可达距离”并不是“某一条具体路径的最远点”而是“所有可达路径能够触及的边界上界”。设想你站在下标 0你可以跳到若干个位置这些位置里最远的一个是 A换个角度只要maxReach没变无论你选择跳到哪个位置未来能覆盖的范围都一定被“跳到最远位置”这个选择所包含。因为跳跃能力是累加的到达一个更远的位置意味着它前方所有位置都更早被纳入可达区间而跳到一个较近的位置可能会多出一个“二次跳跃”的机会但这个机会的最远上限不会超过从更远位置继续跳的上限吗注意这里有一个反直觉的点跳得远不代表下一步跳得更远因为nums[A]可能很小而nums[B]可能很大。所以“只跳到最远位置”这个策略本身并不能保证最优。那我们为什么还能使用贪心因为我们没有在“具体跳到哪里”上做决定。我们只是在遍历时把所有可达位置的潜力都收集起来取一个最大值。换句话说我们维护的maxReach是所有可达位置nums[i] i的集合最大值。这个最大值本身就是全局信息经过动态更新后的结果而不是靠一次局部贪婪决策得到的。所以严格来说这不是“每步选最优动作”的行动贪心而是“实时汇总所有可行选项的潜力上界”的扫描贪心。这也是为什么它一定正确只要某个位置可达它的跳跃潜力就会被计入候选候选的最大值当然不会漏掉任何可行路径。如果需要从更正式的层面理解可以这样看设R(i)表示遍历到下标 i 时累计的最远可达边界我们证明一个不变式——「所有下标小于等于 R(i) 的位置都可达」。初始化R(0) nums[0]显然下标 0 到nums[0]的位置都可达。当遍历到 i 且 i R(i-1) 时i 可达因此 i 到 i nums[i] 之间的位置都可达所以R(i) max(R(i-1), i nums[i])维持不变式。整个过程没有做任何“排除”操作所有可达位置都被保留下来因此最终若R(n-1) n-1则 n-1 可达。这套证明思路比“局部最优等于全局最优”的说法更精确也更适合用来向面试官讲清楚自己的解法。2.3 边界条件与易错点边界条件往往比算法本身更容易让人翻车。我总结了几个高频易错点全都亲测踩过。第一个是数组长度为 1 的情况。nums [0]起点就是终点不需要任何跳跃答案应该是 true。如果代码一上来就判断nums[0] 0就返回 false就会在这里翻车。正确做法是初始化maxReach 0在遍历到下标 0 时更新maxReach max(maxReach, 0 nums[0])然后判断maxReach 0自然得到 true。或者直接开头加一行if (n 1) return true;也行但更建议让主流程自然覆盖这种情况逻辑更统一。第二个是“遍历到 i 时 i 已经超出 maxReach”的判断位置。有些人喜欢在循环开头判断也有人在循环尾部判断两种写法都行但要注意不能漏。如果漏了判断nums[i]可能本身就是一个不可达位置的索引用它来更新maxReach就会虚增边界导致最终错误地返回 true。我见过不少错误代码就是因为在不可达位置仍然执行了maxReach max(maxReach, i nums[i])这行。第三个是浪费较多时间的“0 值陷阱”。nums [1, 0, 1]这种情况终点可达吗从 0 跳到 1然后卡死所以是 false。但nums [2, 0, 0]呢从 0 直接跳两步到终点答案是 true。0 本身不是问题问题是 0 所在的位置“是否切断了可达边界向外扩展的可能”。只要maxReach已经覆盖到该 0 位置之后这个 0 就不用管。真正致命的是maxReach正好停在一个 0 的位置上而后面还有没到达的区域——此时再往后遍历任何一个下标都会出现i maxReach从而正确返回 false。3. 代码实现与实操过程3.1 Python 实现及逐行注释说思路再多不如直接看代码。我用 Python 写一版最标准、最容易记忆的贪心实现并把每一行的意图都讲清楚。from typing import List class Solution: def canJump(self, nums: List[int]) - bool: 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之后立刻判断终点覆盖可以避免后面无意义的循环。第二return True放在循环外面是为了处理 n1 的情况因为循环只执行一次max_reach更新为nums[0]后判断max_reach 0成立直接返回 true。第三如果不想提前返回也可以在循环结束后统一return max_reach n - 1效果完全一样。有同学可能会问提前返回会不会漏掉某些情况答案是不会。因为max_reach已经覆盖终点从可达区间内必然存在一条路径到达终点后续的位置信息已经不再需要了。这个“一旦覆盖终点就立即结束”的思路在很多区间类问题上都能用。3.2 Java 与 C 版本参考用 Java 写这道题整体结构几乎相同只是语法层面略有差别。我直接贴一个常用版本class Solution { public boolean canJump(int[] nums) { int maxReach 0; int n nums.length; for (int i 0; i n; i) { if (i maxReach) { return false; } maxReach Math.max(maxReach, i nums[i]); if (maxReach n - 1) { return true; } } return true; } }C 版本同样简洁class Solution { public: bool canJump(vectorint nums) { int maxReach 0; int n nums.size(); for (int i 0; i n; i) { if (i maxReach) return false; maxReach max(maxReach, i nums[i]); if (maxReach n - 1) return true; } return true; } };三个语言版本的逻辑完全一致先判断当前位置是否可达再用当前位置扩展边界最后检查是否已经覆盖终点。代码量都在十行左右背起来也不难。真正的关键还是理解为什么不能把“更新边界”和“判断终点”两个操作的先后顺序搞反。3.3 复杂度分析与面试追问时间复杂度 O(n)因为我们只遍历数组一次每次操作都是常数时间。空间复杂度 O(1)只使用了一个额外变量maxReach。这是这道题的最优解再想优化已经没有下探空间。面试时经常有追问环节我整理过几个高频追问点提前准备好会从容很多如果数组中有负数怎么办题目明确说了非负整数数组所以不用考虑。但如果真的出现负数意味着“跳跃后退”成为可能问题性质会发生变化贪心不再直接适用。能不能从终点反向跳跃判断可以。思路是从终点往前找“能到达当前位置”的最左起点如果能一路找到下标 0就返回 true。时间复杂度同样是 O(n)但代码逻辑略有不同可以作为拓展思路讲给面试官听。如果要求输出具体路径怎么办贪心只能判断可行性不能给出路径。输出路径需要记录每个位置从哪个位置跳过来通常用动态规划回溯或者用贪心加“从终点向起点反推”的方式复杂度会提升到 O(n²) 或 O(n log n)。3.4 测试用例与验证方法我平时刷题有个习惯做完后不只跑示例还会自己构造多组边界测试。针对这道题我建议至少准备以下几种单元素数组[0]和[5]都应该返回 true。全零数组且长度大于 1[0, 0]返回 false因为起点就是 0根本跳不出去。经典 true 用例[2, 3, 1, 1, 4]。经典 false 用例[3, 2, 1, 0, 4]。“0 在中间但能被跳过”的用例[2, 0, 0]返回 true。“0 在中间且堵死去路”的用例[1, 0, 1]返回 false。极大值用例[1, 1, 1, ..., 1]每个位置只跳一步能一路到达终点应该返回 true。把这些用例都跑一遍基本能覆盖 99% 的边界问题。如果本地测试发现某个用例结果不对不要急着改代码先用打印日志的方式把i、max_reach在每个循环步骤中的值打出来观察边界判断顺序是否正确。4. 常见问题与排查技巧实录4.1 典型错误把“最大步长”和“必须跳这么远”混为一谈这是我见过最多人犯的错误甚至有些刷题超过一百道的人第一次做这道题也会被绕进去。比如nums [2, 1, 0, 3]如果你认为“从下标 0 必须跳 2 步”那么下一步到下标 2值是 0就卡死了于是输出 false。但事实上你可以从下标 0 先跳 1 步到下标 1再从下标 1 跳 1 步到下标 2——等等下标 2 的值还是 0还是卡死。换一条路径从 0 跳 2 步到下标 2卡死。从 0 跳 1 步到下标 1再从下标 1 跳到下标 3下标 1 的值是 1只能跳 1 步所以最远到下标 2到不了 3。因此这个用例确实是 false。但只要把数组改成[2, 1, 1, 3]从 0 跳到 1再从 1 跳到 2再从 2 跳到 3答案是 true。如果你用“必须跳最大步长”的思维会从 0 直接到 2然后从 2 到 3也能得到 true虽然路径不同但结果碰巧对了。但一旦换成[2, 1, 0, 3]两种思维就会产生分歧。刷题时一定要以“每步可以选择 1 到 nums[i] 之间的任意步数”为基准来思考千万别把题意理解窄了。4.2 死循环与无穷迭代问题贪心解法本身不会死循环因为 for 循环的i是单调递增的。真正可能出现“死循环错觉”的是一些变体写法比如用 while 循环维护current指针current 0 while current n - 1: current max(current nums[current], ???)这样的写法如果不能保证每次都前进就会陷入原地打转。例如nums [1, 0, 1]如果current停在 0current nums[current]还是 1然后更新到 1但下一步nums[1] 0又退回来或者不前进就出现循环卡死。用 for 循环天然规避这个问题因为即使你无法前进循环也会继续走到下一个下标并在那里触发i max_reach判断直接返回 false。所以我强烈建议用 for 循环实现不要用 while 手动控制指针。4.3 比较符号的边界问题代码里有两个关键的比较符号写错一个结果就可能偏差。第一个是if (i maxReach)。注意这里是而不是。因为i maxReach时当前位置恰好处于最远边界上它是可达的。如果你写成会误杀“刚好在边界上”的位置导致[1, 1]这种用例从 true 变成 false。我当初就在这个符号上栽过一次排查半天才发现是等号问题。第二个是if (maxReach n - 1)。这里必须包含等号因为终点下标是n - 1只要边界达到终点就说明终点可达。如果写成那么在“恰好一步一步走到终点”的用例上会出错。建议把这两个比较符号作为代码审查的重点检查项。肉眼检查很容易忽略但如果用测试用例覆盖到位这类问题几乎都能暴露出来。4.4 从“记忆化回溯”到“贪心”的移植经验我知道有些朋友是先学了动态规划再回头刷 Hot 100看到这道题容易先入为主。我自己的经历是第一版代码用记忆化搜索能 AC但代码量大了一倍而且时间表现也不如贪心。后来我尝试自己推导贪心发现一个非常实用的思考方法把数组想象成一条跑道你手里只有一个“探照灯”每到一个新位置就用这个位置的电力把探照灯往远推一格。只要探照灯一直没有停住你就能一路向前。这个画面感一旦建立代码写起来就是顺手的事情。如果记不住贪心推导过程还有一个很笨但有效的办法先把测试用例画在纸上用一个箭头表示maxReach手动模拟一遍循环你会发现它每一步都在扩张边界直到覆盖终点或者停住。模拟两遍之后整个算法的直觉就长在脑子里了。5. 跳跃游戏系列的扩展与面试延伸5.1 跳跃游戏 II从“能否到达”到“最少几步”Hot 100 的第 45 题“跳跃游戏 II”是这道题最直接的升级版。题目要求返回到达最后一个下标所需的最少跳跃次数。同样是贪心思路但需要维护两组变量当前可达的边界currentEnd和下一步可达的边界nextMax。遍历数组时先用当前位置更新nextMax当i currentEnd时说明本段已经走到头必须跳一次然后把currentEnd更新为nextMax跳跃次数加一。这个变体的核心是“层序跳跃”思想每一跳覆盖一个区间下一跳覆盖的区间是当前区间内所有位置的跳跃潜力最大值。理解了跳跃游戏 I 的maxReach思想跳跃游戏 II 的思路其实就是多记录一个“当前层终点”。两题放在一起对比刷比单独刷一道效果要好得多。如果你用动态规划做跳跃游戏 II复杂度 O(n²)虽然能过但面试官大概率会追问贪心优化。建议直接把两道题的贪心解法作为一个系列一起准备效率和熟练度都能上一个台阶。5.2 更多变体与同类题型LeetCode 上还有“跳跃游戏 III”1306 题它的跳跃方式是固定的“向前 nums[i] 步或向后 nums[i] 步”这就不再是区间覆盖问题而是图上的可达性问题需要 BFS 或 DFS 来解决。这种题型放在一起看能帮助理解“区间类跳跃”和“图结构跳跃”的本质区别。另外很多面试题会把这道题包装成实际场景比如“能量补给站”“跳石头过河”等。无论包装成什么样只要核心是“每个位置有最大步长判断是否可达”解法就是维护最远边界。识别题型比记住代码重要得多。5.3 实际编码中的应用与启示说实话这种纯算法题在日常业务开发中直接使用的场景不多但它训练的能力非常实用判断一个区间是否能够不断扩展直到覆盖目标。比如在任务调度里判断“当前已分配的资源能否覆盖所有待处理任务”在日志分析里判断“起点时间加上处理耗时能否覆盖整个时间窗口”本质上都是同样的区间扩张思维。我自己在做一些数据处理工具时遇到过“从起始记录出发根据每条记录的关联范围判断能否覆盖整个数据集”的需求第一时间就想到了这道题的贪心套路。它能让你在阅读别人的代码或者设计自己的接口时更快识别出“只要维护一个右端点就能搞定”的场景。6. 从调试代码到总结心法代码写完之后我习惯再看一遍自己的提交记录。做这道题时我第一次提交就用了贪心但因为没有处理“恰好卡在 0 上”的用例连续错了两次。第一次是少了i maxReach的判断导致不可达位置参与了边界更新第二次是写成了导致单步跳跃用例失败。两次错误让我对边界判断的印象特别深刻。如果现在让我给一个刚刷到这道题的朋友建议我会说三件事。第一先不要看题解自己尝试用回溯解一遍体会一下“为什么慢”再用记忆化优化一遍体会“为什么还不够最优”最后尝试推导贪心你会发现整个思考链条顺理成章。第二在本地建立一套自己的测试用例集尤其是边界用例不要每次只靠示例。第三把这道题和跳跃游戏 II 放在一起刷一次吃透一个系列比分散刷十道题更有收获。我个人在实际操作中的体会是刷题不只是为了应付面试更重要的是建立“通过边界条件快速判断算法可行性”的直觉。这道题就是一把非常好的钥匙能帮你打开“区间覆盖 贪心”这扇大门。门后面的跳跃游戏 II、视频拼接、合并区间全都可以用类似的思想串联起来。希望这篇文章能让你少踩一些我踩过的坑也欢迎你有自己的独特解法时拿来找我一起讨论。