刷力扣题单的朋友应该都有这种体验有些题看名字觉得是送分题点进去才发现全是坑。跳跃游戏2就是这样一道题。它挂在力扣100题单的第79位题目本身一句话就能说清楚给定一个非负整数数组你站在第一个下标上每个元素代表你在这个位置最多能往前跳多远问到达最后一个下标最少需要跳几次。但就是这么一句话能把贪心策略、区间覆盖、边界处理这些考点全给你串起来。这题适合所有正在刷力扣100、备战笔试面试的人也适合那些贪心算法总是靠猜、一换数据就翻车的人。我自己当初做这道题第一次想当然地写了个“每步跳最远”的版本自测了好几个用例都没发现问题直到遇到一个反例才意识到路走歪了。后来把“区间覆盖”的思想捋清楚才发现这道题的本质不是“每一步怎么跳”而是“每一跳能覆盖到哪”。这篇文章把我从错误思路到正确解法的完整过程写出来包括正反向两种贪心写法、五个最容易踩的边界坑以及我从这道题里总结出来的题型套路。1. 先把题目读透跳跃游戏2到底要我们做什么1.1 题目描述与示例给你一个非负整数数组 nums你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个下标。假设你总是可以到达数组的最后一个位置。直接看两个例子输入 nums [2,3,1,1,4]输出 2。正确路径是下标0跳到下标1跳2步再从下标1跳到下标4跳3步一共2跳。注意从下标0也可以直接跳到下标2但那样后面就得绕路步数反而多。输入 nums [2,3,0,1,4]输出 2。下标0跳到下标1再跳到终点。有一个很容易忽略的前提条件题目保证一定可以到达最后一个位置。这意味着你不需要额外判断“不可达”的情况所有测试用例都是能到终点的。这个保证有什么意义后面写代码时你会意识到少了这个保证你还得多写一层边界判断如果遍历过程中当前下标已经超过了能到达的最远位置说明卡死了。但既然题目保证可达这个分支就可以省掉。1.2 这题和第一代跳跃游戏的核心区别力扣题单里通常把跳跃游戏放在一起第一代是“跳跃游戏1”问的是能不能到达终点第二代才是这个“跳跃游戏2”问的是最少几步。很多人以为二代只是在一代基础上加个计数器实际写起来才发现完全不是那回事。一代的思路很简单维护一个最远可达位置 maxReach遍历数组时不断更新它如果发现当前下标已经大于 maxReach说明中间断档了返回 false。整个过程只需要关心“覆盖范围”能不能延伸到终点。二代多了一个步数统计难就难在“什么时候步数加一”。你可能会想这还不简单吗每次把最远可达位置更新了就加一次。我当初也是这么想的结果算出来的步数要么偏大要么偏小。原因在于跳跃并不是每次更新 maxReach 都发生一次而是在“当前这一跳覆盖的区间已经全部检查完”的时候才必须做出下一跳的决策。这个时机的把握就是整道题的核心考点。2. 贪心思路为什么“每步跳最远”是错的2.1 一个反例贪最远反而吃亏刚拿到题绝大多数人的第一反应是贪心嘛每次都跳到当前位置能跳到的“最远下标”这样总步数肯定最少。这个直觉听起来非常合理但它是错的。来看反例 nums [2,3,1,1,4]站在下标0nums[0] 2能跳到的位置是下标1和2。按“跳最远”的贪心你应该跳到下标2。到了下标2nums[2] 1只能跳到下标3。到了下标3nums[3] 1只能跳到下标4。终点到了但一共跳了3步。然而正确答案是2步下标0跳到下标1这个位置nums[1] 3然后再从下标1一步直接到终点。问题出在哪站在下标0时只比较“这一步能跳多远”是不够的你得看下一步还能跳多远。下标1虽然第一步比下标2少跳一格但它下一步的潜力比下标2大得多。这说明局部的“最远”并不对应全局的“最少步数”。如果贪心这么简单这题也不配排在力扣100里了。这个反例特别值得记下来。刷题的时候一旦你提出一个贪心策略最好先在脑子里过一遍“这个策略是不是只盯着当前这一步的收益而忽略了下一步的收益”如果是那大概率有反例等着你。2.2 正确的贪心只看区间覆盖范围正确的贪心并不是“每次跳最远”而是“每次都让当前这一跳的覆盖区间最大化”。我换个方式解释。站在下标0时你第一跳能到达的不是某一个点而是一个区间从下标0到下标0 nums[0]。在这个区间内的任意一个位置都可以作为第二跳的起点。那么第二跳最远能到哪取决于这个区间内所有位置的“潜力”也就是每个位置 i 的 i nums[i] 的最大值。所以决策逻辑变成第一跳落在哪个位置并不重要重要的是第一跳落地后第二跳的起点集合覆盖了多少范围。只要这个范围达到最大你就能保证总步数最少。这就好比坐公交换乘你关心的不是第一站到哪而是换乘之后能覆盖哪些站。真正聪明的做法是在当前可达的所有站点里选一个能让你后续覆盖范围最大的站作为换乘点而不是选一个“跑得最快”的站点。这种“把一步看成一个区间而不是一个点”的视角是解出这道题的关键也是我后来做其他区间类题目时反复使用的思维模型。3. 正向区间覆盖法最经典的 O(n) 写法3.1 核心变量与判定逻辑现在把上面的思路翻译成代码。整段逻辑只需要三个变量end当前这一跳覆盖区间的右边界。也就是“不增加跳跃次数最远能到达的下标”。farthest在扫描过程中从当前区间内所有位置出发能到达的最远下标。ans已经使用的跳跃次数。遍历数组时每一步都做两件事。第一件事用当前位置的潜力去刷新 farthest即 farthest max(farthest, i nums[i])。第二件事判断当前下标 i 是否已经到达了 end也就是当前这一跳的覆盖边界。如果 i end说明当前这一跳能覆盖的所有位置都已经检查完了再往下走就必须多跳一次此时执行 ans 1并把 end 更新为 farthest表示我把下一跳的覆盖区间扩大到了之前算出的最远位置。你可能会有疑问为什么不在每次更新 farthest 的时候都加一次步数因为那样就把“潜在最远距离”误当成了“实际跳跃距离”。farthest 只是告诉你“如果我们愿意多花一跳最远能到哪”但真正决定要不要花这一跳的是当前区间是否已经到头。end 的更新时机是这道题最容易写错的地方也是整道算法的灵魂。3.2 代码实现Python 版本from typing import List def jump(nums: List[int]) - int: n len(nums) if n 1: return 0 ans 0 # 最少跳跃次数 end 0 # 当前这一跳能到达的右边界 farthest 0 # 扫描过程中能到达的最远位置 for i in range(n - 1): # 注意是 n - 1不是 n farthest max(farthest, i nums[i]) if i end: ans 1 end farthest return ans代码非常短但每一行都有讲究。拿示例 [2,3,1,1,4] 手动走一遍i 0farthest max(0, 02) 2i ! endend 0没触发跳跃。i 1farthest max(2, 13) 4i ! endend 0没触发跳跃。i 2farthest max(4, 21) 4i endend 0 不对这里 end 还是0吗不是之前没有触发过跳跃end还是0但 i2 和 end0 不相等。重新走一遍。重新正确走一遍注意 end 初始为0所以 i0 时 i end 成立循环一开始就会触发第一次跳跃这里需要重新考虑。按上面的代码i0 时 farthest2且 iend00所以 ans1end2。这一步代表什么代表“从0出发第一步的最远覆盖是2”。ans 变成1是正确的因为你至少需要第一跳才能离开下标0。然后i 1farthest max(2, 13) 4i ! endend2。i 2farthest max(4, 21) 4i end22ans2end4。i 3farthest max(4, 31) 4i ! endend4。循环结束i n-1n-13所以 i 最大到3返回 ans2。这下就对了。关键是理解 i0 时的一次跳跃计数它代表你站在起点时第一跳的覆盖边界已经确定为 nums[0]。之后遍历到该边界时再增加一跳。3.3 为什么循环只要走到 n-2这是新手最容易纠结的地方为什么循环条件是 range(n - 1)而不是 range(n)因为最后一个下标是终点不需要跳跃。循环遍历到终点之前的所有位置目的是计算“从这些位置出发最远能到哪”。当你遍历到 i n-2 时已经覆盖了终点前的一切可能性。如果循环范围是 range(n)那么当 i 遍历到最后一个位置时执行 if i end 可能会多跳一次导致答案比真实值大 1。另外还有一层理解我们不是在“最后一步前”跳跃而是在“当前区间耗尽时”跳跃。终点一定落在某个区间的覆盖范围内当你把这个区间完整扫描完时步数已经加上了不需要在终点位置再做任何操作。所以遍历到 n-2 就够多遍历一个纯属给自己找麻烦。我在本地测试时特意把 range(n - 1) 改成 range(n)用 [0] 和 [2,3,1,1,4] 分别跑结果 [2,3,1,1,4] 输出了3而不是2。这就是“在终点处误触发一次跳跃”的典型症状你以后如果遇到输出偏大1的情况第一反应就应该是这个。4. 反向跳跃法与贪心的另一种视角4.1 反向贪心的思路正向覆盖法已经是这道题的最优解了时间复杂度 O(n)空间复杂度 O(1)。但我还是建议你花五分钟了解一下反向贪心因为它提供了另一种理解角度而且思维负担更小。反向贪心的逻辑很直接从终点倒着往起点找。假设当前目标是下标 pos我要找的是前面某个下标 i满足 i nums[i] pos也就是从 i 能一步跳到或跳过 pos。在所有这样的 i 里面选择下标最小的那个作为下一步的起点然后步数加一把 pos 更新为 i重复这个过程直到 pos 到达下标0。为什么选下标最小的因为下标越小说明这个位置越靠前它的可达范围通常覆盖了后面更多的位置更有可能通向起点。当然这里有贪心的成分选择“离起点最近”的可达位置本质上是让下一步的搜索范围最大。4.2 代码实现与复杂度对比def jump_reverse(nums: list[int]) - int: n len(nums) pos n - 1 steps 0 while pos 0: for i in range(pos): # 从起点开始找最早能跳到 pos 的位置 if i nums[i] pos: pos i steps 1 break return steps这段代码好理解但性能差一些。每找一跳都要从头扫描到 pos最坏情况下时间复杂度是 O(n^2)。比如数组是 [1,1,1,1,1,1] 这种每一跳都得从头扫一遍。所以在力扣上提交时用正向 O(n) 解法就好反向思路更适合用来理解贪心的核心每次都做“基于当前信息的局部最优选择”。我把两种方法放在一起对比一下。对比维度正向区间覆盖法反向跳跃法核心思想维护当前区间覆盖边界区间耗尽时步数加一从终点倒推每次找能到达当前目标的最靠前位置时间复杂度O(n)最坏 O(n^2)平均接近 O(n)空间复杂度O(1)O(1)理解难度稍难需要理解 end 和 farthest 的关系直观好写但性能劣势明显易错点循环范围写错、end 更新时机错while 死循环、找最小下标时 break 位置错学到这里你可能会发现贪心算法很多时候不是“一步到位选最优”而是“在当前可选集合中选一个能最大化后续收益的选项”。正向解法里的 farthest 就是这个“后续收益”的量化指标。5. 实战中的易错点与调试实录5.1 六个高频边界错误我拿这道题问过不少一起刷题的朋友也看过网上各种题解区里的提问发现错误几乎集中在下面几类全列出来帮你避坑。第一循环范围写成 range(n)。后果是终点可能被当成“需要继续跳跃的位置”额外触发一次 ans 1答案偏大。解决办法牢记终点不需要跳循环到 n-2 即可。第二end 的更新时机搞错。有人把 end 放在每次更新 farthest 时同步更新而不是在 i end 时才更新。这样做的后果是步数会被过早加上。举个例子 [3,1,2,1,1]下标0覆盖到3下标1的潜力还不够但下标2潜力足够。如果每次更新 farthest 都更新 end那在下标1时步数就加了导致最终答案偏大。记住一个口诀end 只在 i 走到当前覆盖边界时才变。第三忘了处理 n 1 的情况。数组只有一个元素时已经在终点不需要任何跳跃答案是0。如果你不写这个判断循环从 0 到 n-2 根本不会执行ans 初始是0其实也没问题。但如果你把 ans 初始化成1就错了。所以要么单独判断要么把 ans 初始值设为0且不要画蛇添足。第四使用了错误的贪心策略即“每次跳最远”。这个错法在第2章已经详细说过最容易在面试时暴露因为面试官只要换一组数据就能戳穿你。建议把 [2,3,1,1,4] 这个反例背下来至少能帮你自查。第五把 nums[i] 理解成“下一步的固定跳跃距离”。注意题干说的是“最大长度”也就是说从 i 出发可以跳任意不大于 nums[i] 的步数。表达式应该是 i nums[i]而不是 nums[i] 本身。我用 Python 写的时候还经常把 i 忘了加进去导致覆盖距离少算一大截。第六在 i end 的分支里有人会把 end farthest 写成 end i nums[i]。这两者在当前 i 恰好是区间内潜力最大的位置时才相等其他情况下前者大于后者。end 是用来描述“下一跳覆盖整个区间的上限”的如果不使用全局最大值 farthest就会缩小搜索范围步数偏大。5.2 一个真实调试过程我自己在写这道题的时候第一次版本长这样def jump(nums): n len(nums) ans 0 end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i end: end farthest ans 1 return ans这个版本其实是对的。但我在早期写过一个错误版本把 if i end 写在了 farthest 更新之前也就是for i in range(n - 1): if i end: ans 1 end farthest farthest max(farthest, i nums[i])问题很明显在下标 i 等于 end 时farthest 用的还是上一轮的数据没有包含当前这一点的信息。比如 [2,3,1,1,4] 在 i2 时end 是2但 farthest 还没更新到4因为更新放在后面导致 end 被设置成2而不是4答案就直接错了。当时我用 print 把每一步的 i、farthest、end 打印出来才定位到这个顺序问题。所以调试这类贪心题最有效的办法不是看最终返回值而是把变量变化轨迹逐行打印出来。打印代码很好写for i in range(n - 1): farthest max(farthest, i nums[i]) if i end: print(fi{i}, farthest{farthest}, jump now) ans 1 end farthest看到 i 和 farthest 是否同步变化基本一眼就能找到问题。6. 把题目吃透相关题型与套路总结6.1 跳跃游戏全家桶做透这一题之后你会发现它其实是一个“区间覆盖”思想的典型代表。力扣里的跳跃游戏系列刚好形成了一条清晰的能力进阶路线。跳跃游戏1是判断能否到达终点。它只需要维护一个 maxReach遍历时如果当前位置超过了 maxReach 就返回 false否则持续更新。核心代码不超过十行适合用来理解“覆盖范围”概念。跳跃游戏2就是我们这篇的主角在覆盖范围的基础上增加了步数统计核心是玩转 end 和 farthest 两个变量。跳跃游戏3就变了个形式从一个起点出发每次可以向左或向右跳 nums[i] 步问能否到达某个值为0的下标。这题不再适合贪心标准解法是 BFS 或 DFS。你会发现同样叫“跳跃游戏”但底层算法的选择完全取决于问题的约束和查询的目标。把这三道题放到一起做一遍你对“什么类型的问题用贪心什么类型问题要搜索”会有非常直观的感受。6.2 从这题衍生出的区间覆盖思想跳出跳跃游戏的范畴这种“维护一个当前覆盖区间用最远可达距离扩展下一个区间”的套路在很多题里都能看到。最典型的是合并区间类题目先把区间按左端点排序然后遍历时维护当前合并区间的右边界如果新区间的左端点小于等于当前右边界就扩展现有区间否则开启新区间。这里的“当前右边界”就跟跳跃游戏里的 end 是一回事。另一个类似的是会议室安排相关的贪心题在所有可选会议中每次都选结束时间最早的会议因为它能为后续留下最多空间。这跟跳跃游戏“选择后续覆盖最大的落点”在精神上是完全一致的局部选择要服务于未来收益而不是当下刺激。所以我的建议是刷完跳跃游戏2不要急着往下走花一小时做两道区间合并的变体题把 end 和 farthest 的逻辑迁移过去。一旦你形成“区间覆盖”的心智模型以后再遇到这类题读题读完基本就能确定解法方向剩下的只是代码细节。最后分享一个我个人的实操体会。最初我以为这题考的是“贪心算法的正确性证明”后来被反例教育过一次才明白它考的是“怎么设计一个状态变量来描述决策边界”。end 和 farthest 这两个变量一个描述现在一个描述未来现在的边界耗尽时未来就变成新的现在。这个模型不仅适用于这道题也适用于很多“至少需要多少次操作才能覆盖目标范围”的问题。如果你现在还在纠结为什么代码只有十行却想不通别急把 [2,3,1,1,4] 这个反例在纸上画三遍把每个位置的覆盖区间画成线段你就能直观看到 end 怎样一步步被推到终点。在我看来这才是这题最值得学会的东西。