企业官网建设流程全解析

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：继续扫描当前覆盖区间时，用一次额外跳跃能到达的最远位置。

初始化时，起点下标0，jumps = 0，currentEnd = 0，farthest = 0。

然后开始扫描i。每走到一个下标i，先计算farthest = max(farthest, i + nums[i])。如果i到达了currentEnd，说明当前这一层已经扫描完了。下一步必须用一次新的跳跃，所以jumps++，同时把currentEnd更新为farthest。

这个逻辑非常关键：currentEnd不是当前下标，而是“当前跳跃次数已经能覆盖到的右边界”。你人不必正好站在currentEnd上，它只是一个边界标记。

2.2 为什么这个贪心选择是正确的

贪心的核心是“边界推得越远，一定不会更差”。

假设已经用了k次跳跃，能覆盖的范围是[0, currentEnd]。下一次跳跃可以从这个范围里的任意位置开始。那么第k+1次跳跃最多能覆盖到多远？答案就是：

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 = 0，currentEnd = 0，farthest = 0。

第一步，i = 0。计算farthest = max(0, 0 + 2) = 2。此时i == currentEnd == 0，当前层扫描完毕，必须使用一次跳跃，于是jumps = 1，currentEnd = 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 = 2，currentEnd = 4。现在最远边界已经到达终点，循环可以结束，答案是2。

把完整过程整理成表格更清楚：

这个例子虽然小，但已经把整个算法的骨架跑完了。每次i碰到currentEnd，就意味着“当前跳跃次数能覆盖的区域已经全部检查完毕，下一步必须跳了”。

3.3 再换一个例子验证：[1, 2, 1, 1, 1]

很多人看一个例子觉得懂了，但代码写出来还是会乱，因为边界更新的时机不够熟练。我们再跑一个例子：nums = [1, 2, 1, 1, 1]，长度5，终点下标4。

过程如下：

• i = 0：farthest = max(0, 0 + 1) = 1，i == currentEnd == 0，所以jumps = 1，currentEnd = 1。
• i = 1：farthest = max(1, 1 + 2) = 3，i == currentEnd == 1，所以jumps = 2，currentEnd = 3。
• i = 2：farthest = max(3, 2 + 1) = 3，i != currentEnd，不加次数。
• i = 3：farthest = max(3, 3 + 1) = 4，i == currentEnd == 3，所以jumps = 3，currentEnd = 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变成1，currentEnd还是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的关系就不会混淆，代码的边界条件也会自然写对。希望这篇图解能帮你把这道题的贪心逻辑彻底吃透。