1. 从题意说起这题到底在问什么LeetCode 45“跳跃游戏 II”是贪心算法里非常经典的一道中等题也是很多面试官喜欢让候选人现场手写代码的题目。题目给一个非负整数数组nums你从下标0出发nums[i]表示你在下标i这个位置最多能向前跳多少步注意是“最多”不是必须跳这么远。要求计算最少跳几次能到达最后一个下标n - 1题目保证一定能到达。我最早刷这道题时第一反应是暴力搜索从每个位置把所有可能的落点都枚举一遍然后找最短路径。这个思路本身没错但数组稍微长一点就会超时因为分支太多。后来把跳跃过程看成“区间扩张”之后我才真正明白为什么一个O(n)的循环就能搞定而且代码短到可以直接背下来。这道题适合谁看如果你是刚开始刷算法的同学或者在准备面试时复习贪心思路这篇文章都值得读一遍。我会把每一步变量怎么变、为什么这么变、边界条件在哪里容易踩坑都拆开讲清楚还会用图示把[2, 3, 1, 1, 4]这个经典例子完整跑一遍。1.1 先搞清三个关键点第一nums[i]是一个上限。比如nums[0] 2表示从下标0出发可以跳到下标1也可以跳到下标2。所以单个位置并不是一个固定落点而是“有一个可达范围”。第二跳跃方向只能是向前下标只能越来越大。你不能跳回之前的位置所以这道题本质上是在一个有向的线性结构里找最短路径。第三目标不是走到某个固定值而是到达最后一个位置n - 1。也就是说只要某次跳跃能覆盖到n - 1就已经完成任务了。1.2 从“能跳多远”变成“能覆盖多长”因为每个位置都有一条“最大射程”从下标i出发最远能到的位置是i nums[i]。所以站在某个位置时你不必纠结具体跳到哪一个点只需要关注下一步的边界能推进到哪里。这就像一张旧地图你已经知道的区域是从当前位置到某个边界currentEnd在这个区域里任意一个位置都可以成为下一次起跳点。我们扫描这个区域里的所有位置不断更新“下一次最远能覆盖到哪里”也就是maxReach。当扫描完整个当前区域时把边界换成maxReach跳跃次数加一这就是整道题的核心逻辑。用生活化的话说你从起点出发第一跳能覆盖一段路在这段路上不管落在哪里真正重要的是第二跳能覆盖多远。你不需要现在决定“我到底落在哪个点”因为在这段路里所有点都已经能到达了。1.3 为什么不用动态规划穷举如果对每个位置都试所有可能的跳法很容易写出dp[i] min(dp[j] 1)的转移方程其中j能跳到i。这个做法的复杂度是O(n^2)在n很大时会超时。而且这个问题的结构比较特殊跳跃区间是连续的可以用贪心把状态压缩成两个变量没必要把所有子问题都算一遍。后面我会详细证明只要每一步都让边界覆盖得尽可能远跳数一定是最小的。这个结论看着简单但要理解它背后的“层”思想不然面试时一紧张就容易把代码写错。2. 贪心策略的核心推导2.1 把跳跃过程看成一层一层推进想理解这道题的贪心最舒服的角度是把跳跃当成 BFS 的层序遍历。我们用三次跳到达的位置范围就是第 3 层的节点。由于每一层都是连续区间我们只需要记录这一层的最右端点和下一层能扩展到的最右端点。具体来看这三个变量jumps已经用了多少次跳跃。currentEnd在用了jumps次跳跃后能覆盖到的最远位置。farthest继续扫描当前覆盖区间时用一次额外跳跃能到达的最远位置。初始化时起点下标0jumps 0currentEnd 0farthest 0。然后开始扫描i。每走到一个下标i先计算farthest max(farthest, i nums[i])。如果i到达了currentEnd说明当前这一层已经扫描完了。下一步必须用一次新的跳跃所以jumps同时把currentEnd更新为farthest。这个逻辑非常关键currentEnd不是当前下标而是“当前跳跃次数已经能覆盖到的右边界”。你人不必正好站在currentEnd上它只是一个边界标记。2.2 为什么这个贪心选择是正确的贪心的核心是“边界推得越远一定不会更差”。假设已经用了k次跳跃能覆盖的范围是[0, currentEnd]。下一次跳跃可以从这个范围里的任意位置开始。那么第k1次跳跃最多能覆盖到多远答案就是max(i nums[i])其中i属于[0, currentEnd]。如果在某次选择里你选了一个落点导致下一次最远边界比这个最大值小那么这个方案绝对不会比达到最大值的方案更早到达终点。因为边界是一个单调覆盖关系边界越大能作为下一次起跳点的位置越多后面的选择只会更自由。换句话说在所有可能的“下一次跳跃终点”里我们关心的是“这些终点能再往前放射出的最大范围”。你可以在当前覆盖区间里优哉游哉地走但下一条边界必须是所有可达位置的最大发射范围。这就是贪心选择性质的直观证明。2.3 容易踩的坑不是“每步跳最远的位置”很多人刚开始会误以为贪心就是“每次从当前位置跳到最远的下标”这其实是错的。拿[2, 3, 1, 1, 4]来说如果每步都跳到最远下标第一步从下标0跳到下标2第二步从下标2最远能跳到下标3第三步从下标3才能跳到下标4。总次数是3但正确答案是2从下标0跳到下标1然后从下标1直接跳到终点。为什么“每步最远”反而差了因为它只看当前一步能到哪没有看“从这些可达点里下一步能覆盖多远”。下标1虽然第一步跳得不是最远但它下一步的射程1 3 4直接覆盖终点。所以真正的贪心对象不是单个落点而是边界。这个理解一旦到位代码就只是把“扫描当前层扩展下一层”这个逻辑翻译成循环。3. 图解完整流程标准例子跑一遍3.1 用[2, 3, 1, 1, 4]演示区间扩张这个例子是题目自带的标准样例也最容易看出贪心边界的变化。先看数组索引: 0 1 2 3 4 数值: [ 2, 3, 1, 1, 4 ]目标是从下标0到达下标4。初始状态是jumps 0currentEnd 0farthest 0。第一步i 0。计算farthest max(0, 0 2) 2。此时i currentEnd 0当前层扫描完毕必须使用一次跳跃于是jumps 1currentEnd 2。现在我们知道跳一次之后最远能覆盖到下标2。注意这一步结束之后我们没有决定具体落点是下标1还是下标2。这两个位置都在当前覆盖范围内都是合法的下一步起点。这正是“区间”思维和“单点”思维的区别。3.2 扫描第二层更新下一次边界继续循环i 1。farthest max(2, 1 3) 4。此时i是1不等于currentEnd 2所以不增加跳跃次数。这个更新意味着如果第一次跳落到下标1第二次跳跃最远就能到达下标4也就是终点。接着i 2。farthest max(4, 2 1) 4。此时i currentEnd 2当前覆盖区间[0, 2]已经被扫描完所以需要再增加一次跳跃jumps 2currentEnd 4。现在最远边界已经到达终点循环可以结束答案是2。把完整过程整理成表格更清楚当前下标 i更新后的 farthesti currentEndjumps新的 currentEnd02是1214否1224是24这个例子虽然小但已经把整个算法的骨架跑完了。每次i碰到currentEnd就意味着“当前跳跃次数能覆盖的区域已经全部检查完毕下一步必须跳了”。3.3 再换一个例子验证[1, 2, 1, 1, 1]很多人看一个例子觉得懂了但代码写出来还是会乱因为边界更新的时机不够熟练。我们再跑一个例子nums [1, 2, 1, 1, 1]长度5终点下标4。过程如下i 0farthest max(0, 0 1) 1i currentEnd 0所以jumps 1currentEnd 1。i 1farthest max(1, 1 2) 3i currentEnd 1所以jumps 2currentEnd 3。i 2farthest max(3, 2 1) 3i ! currentEnd不加次数。i 3farthest max(3, 3 1) 4i currentEnd 3所以jumps 3currentEnd 4已经到达终点。答案是3。实际路径可以是0 - 1 - 3 - 4也可以是0 - 1 - 2 - 3 - 4前者的确更优。这个例子还说明一个细节并不是每次增加跳跃次数都必须立刻结束循环。只有当更新后的currentEnd n - 1时才能提前结束。如果还没到终点就继续扫描直到下一轮边界覆盖终点。4. 代码实现与复杂度分析4.1 Python 解法短小但每行都有讲究直接看代码def jump(nums): n len(nums) if n 1: return 0 jumps 0 current_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i current_end: jumps 1 current_end farthest if current_end n - 1: break return jumps需要注意循环范围是range(n - 1)也就是只遍历到倒数第二个位置。最后一个位置不需要作为起跳点因为只要到了那里就已经完成任务了。如果当前边界已经覆盖到终点也没有必要再继续扫描。farthest max(farthest, i nums[i])这一步必须放在if i current_end之前。原因很容易被忽略当i current_end时当前位置本身也属于当前覆盖区间它可以作为下一次跳跃的起点。如果先判断再更新就会漏掉当前边界的贡献导致结果偏大。4.2 Java 写法逻辑完全一致面试时经常需要现场写 Java这里也给一个对应版本class Solution { public int jump(int[] nums) { int n nums.length; if (n 1) { return 0; } int jumps 0; int currentEnd 0; int farthest 0; for (int i 0; i n - 1; i) { farthest Math.max(farthest, i nums[i]); if (i currentEnd) { jumps; currentEnd farthest; if (currentEnd n - 1) { break; } } } return jumps; } }这个版本的变量名很长但可读性最好。面试的时候我习惯用currentEnd和farthest这种清晰的名字而不是end、maxReach混着用因为代码写完之后还要跟面试官解释思路变量名本身就是最好的注释。4.3 时间复杂度和空间复杂度为什么是 O(n)整个数组最多被扫描一遍每个下标只进入循环一次所以时间复杂度是O(n)。currentEnd和farthest只是两个整数空间复杂度是O(1)。对比动态规划版本dp[i]需要额外一层循环找前一个起跳点复杂度是O(n^2)。这道题之所以能用贪心本质就是因为跳跃覆盖范围是连续的边界扩张可以压缩成一个简洁的状态。如果题目改成“每步必须跳固定步数”或者“每个位置只能跳到一个固定目标”贪心就不一定成立因为区间连续性被破坏了。所以理解问题结构比背代码更重要。5. 常见问题与踩坑实录5.1currentEnd和farthest到底谁先更新我见过很多人在这一题上写错几乎都是因为把currentEnd当成了“当前位置”。它不是。currentEnd是当前跳跃次数能覆盖的最远边界是一个里程碑不是你的脚所在的位置。farthest是一个临时变量记录在当前这层覆盖区间里用一次新跳跃能达到的最远位置。所以每扫描一个i都要先让farthest尽量变大。等i遇到currentEnd时才把currentEnd提升到farthest。如果先更新currentEnd再算farthest典型错误就是结果偏小。举个例子nums [1, 1, 1]。正确结果应该是两次跳跃0 - 1 - 2。有人把判断放在farthest更新前面循环走到i 0时先把jumps变成1currentEnd还是0然后再算farthest 1。后面i 1时发现currentEnd还是0永远追不上i最后返回一个错误答案。所以不要小看这两行的顺序。5.2 遇到nums[i] 0会不会死循环题目保证一定可以到达终点所以理论上不需要额外处理0。但你还是要知道它意味着什么某个位置不能作为起跳点不代表它不能作为落点。只要它落在某个已覆盖区间内不需要从它出发也能继续前进。如果你希望在无法到达时返回-1可以在循环里加一个判断当i currentEnd时说明当前跳跃覆盖不到当前位置直接返回-1。不过在原题约束下这一步没必要。我在实际写代码时不会主动加因为加了反而可能掩盖题目给的保证条件。5.3 提前 break 会漏掉答案吗不会。当currentEnd n - 1时边界已经覆盖终点说明当前跳跃次数已经足够到达终点。由于我们是按层推进的jumps每次加一都代表“再多跳一次能覆盖到哪里”所以第一次覆盖到终点时的jumps就是最小次数。这个时候 break 只是提前终止不会影响结果。如果去掉 break循环在i n - 1的条件下也不会出现额外加次数的情况因为当currentEnd已经是n - 1时后续的i不可能再等于currentEnd判断条件不会触发。所以 break 只是优化不是正确性依赖。5.4 如何扩展成“输出具体跳跃路径”这道题只要求次数但有些变体或者面试追问会让你打印具体路径。方法是在更新currentEnd时记录“下一跳的最优起点”。大概思路是在扫描i时如果i nums[i]比当前farthest更大就把这个i记录为候选起点当i currentEnd时把currentEnd更新成farthest同时把之前记录的候选起点放进路径中。这样就能重建出一条最少跳跃路径。我自己刷这道题时还有一个习惯先在纸上画出“当前覆盖区间”和“下一覆盖区间”两段再写代码。因为只要脑子里有区间图i和currentEnd的关系就不会混淆代码的边界条件也会自然写对。希望这篇图解能帮你把这道题的贪心逻辑彻底吃透。
