企业官网建设流程全解析

LeetCode 45 跳跃游戏 II 是贪心算法里非常经典的一道题，面上看只是一个数组和下标，实际却把“最少跳跃次数”这个最优化问题，藏在了每个位置的“可跳范围”里。这篇题解不讲虚的，直接从策略推导、图解演算、代码细节、常见坑位一条龙拆完，适合正在刷题准备面试、或者学贪心算法总觉得“差点意思”的朋友。

1. 先看清题目：LeetCode 45 到底在求什么

1.1 从“判断能否跳”到“计算最少跳几次”

这道题有个前作叫跳跃游戏 I，那题只问“能不能跳到最后一个位置”，用的是很直白的覆盖区间判断。而 LeetCode 45 跳跃游戏 II 直接加码：不仅保证你能跳到终点，还要求你用最少的跳跃次数跳过去。

题目描述常见版本是这样：给你一个非负整数数组 nums，你初始在下标 0 的位置。nums[i] 表示你在下标 i 处最多可以往右跳的距离，目标是到达最后一个下标，求最小跳跃次数。题目额外给了一个重要前提：输入保证你总是可以到达数组的最后一个位置。

这个前提很关键，它意味着我们做贪心的时候，不需要额外判断“跳不到终点的失败分支”，可以专注于优化步数。我刷题时看到“总是可以到达”这句话，第一反应是：这题官方是铁了心要考“最优化”，不是考“可行性判断”。想明白这一点，后面选算法方向就不会跑偏。

1.2 直觉方案为什么容易翻车

很多人第一次做这道题，最直观的思路是模拟：从当前下标开始，看看能跳到的位置里，哪个位置上的数值最大，就往那边跳。这个想法听起来很合理，因为“走得远”通常意味着“更接近终点”。

但稍微构造一个用例就能推翻它。比如 nums = [3, 4, 1, 1, 1, 1]。下标 0 能跳到 1、2、3，其中下标 1 的数值是 4，最大，所以直觉会往下标 1 跳。可是从下标 1 跳 4 步最远到下标 5，直接到终点，总共只需要 2 步。这里碰巧对。可如果换成 nums = [3, 2, 1, 1, 4]，下标 0 能跳到 1、2、3，数值最大的是下标 1 的 2，往下标 1 跳，最远到下标 3；再从下标 3 跳 1 步到下标 4，总共要 3 步。而最优解是 0 -> 2 -> 4，只需要 2 步。

问题出在哪？出在“选跳得最远的点”和“选能覆盖更远范围的区间”是两回事。我们追求的是整个跳跃过程的步数最少，不是某一步的单点数值最大。这就像接力赛跑，第一棒选手要找的不是“当前脚下跑得最快的那个人”，而是“让接力棒能够覆盖到更远位置的那条路线”。

2. 贪心策略的推导：用“覆盖区间”思考，而不是“选最远点”

2.1 关键思想：下一跳其实是从一个区间里选的

贪心算法的核心思路，不是决定“这一跳具体落在哪个下标”，而是维护一个“当前步数下能够覆盖到的区间”。我常跟朋友讲，你想象地面上有一根可以伸缩的荧光棒，它的一端固定在你当前的起点，另一端随着你遍历区间内的点，不断往外延伸。

一开始，你在下标 0，步数为 0。根据 nums[0]，第一跳可以覆盖到下标 0 到 nums[0] 之间的所有位置。这个区间右边界叫 curEnd，代表“当前这步跳完，最远能到的位置”。但注意，区间里的每个点都可能有自己的跳跃能力，这些点会告诉你“如果你下一步从它们身上起跳，最远能到哪里”。所以遍历区间里的每个点 i，实时计算 i + nums[i]，把最大值记作 farthest。

当遍历指针 i 走到了 curEnd，说明当前这一“步”的覆盖区间已经看完了，此时必须迈出下一步。下一步的起点可以是区间里的任意一点，我们已经提前算好了所有这些点能触达的最远位置 farthest，所以下一步的覆盖区间右边界就更新为 farthest。同时步数加 1。

整个过程里，我们没有指定“哪个点作为下一跳的起点”，但保证了下一跳一定存在，而且覆盖区间一定是最优的。这就是贪心的精妙之处：用区间代替点，用覆盖范围代替具体路径。

2.2 用一个反例推翻“每次跳最远”

为了说明区间贪心比单点贪心更可靠，再看一个对比：

nums = [2, 1, 1, 1, 1, 1]。

下标 0 的数值是 2，它能跳到下标 1 或 2。如果按“当前可跳点中数值最大”的直觉，下标 1 的数值是 1，下标 2 的数值也是 1，一样大，随便选一个，假设选了下标 1。从下标 1 出发，nums[1] = 1，只能到下标 2；然后从下标 2 出发，nums[2] = 1，到下标 3……直到最后，总共要跳 5 步。

而区间贪心在第一步就发现：从 0 出发，最远能覆盖到下标 2。虽然它不规定你具体跳到哪里，但等指针走到下标 2 时，会更新下一跳覆盖区间的右边界。继续走下去，最终一共跳 4 步或者更少。为什么？因为区间贪心没有把鸡蛋放在某一个“数值最大的点”里，而是整体考虑了区间内所有点的潜力。

这种思路换个角度看，其实是 BFS 的变体：把每一步能到达的位置当成一层，下一跳的范围由当前层所有节点共同扩展。贪心在这里保证了层数最少，因为每一层都是“尽全力往外扩”的。

3. 图解全过程：手把手用示例数组走一遍贪心

3.1 示例数据与变量初始化

拿官方示例 nums = [2, 3, 1, 1, 4] 推演，这是最经典的用例。下标从 0 到 4，数组长度为 5，最终目标是到达下标 4。初始化三个变量：

• steps = 0，记录当前跳跃次数。
• curEnd = 0，表示当前这一跳覆盖区间的右边界，初始在第 0 格。
• farthest = 0，表示遍历过程中发现的、下一步能够到达的最远下标。

你可以把 curEnd 理解成“这一棒已经跑到的位置”，farthest 理解成“下一棒能冲到的位置”。整个算法就是在不断追这个边界。

3.2 逐步拆解：从下标 0 到下标 4

第一跳，遍历 i = 0 到 curEnd = 0。此时只看了下标 0，nums[0] = 2，所以 farthest 更新为 0 + 2 = 2。i 等于 curEnd，说明这一跳的区间结束了，必须跳一次，steps 变成 1，curEnd 更新为 farthest 也就是 2。此时覆盖区间变成下标 0 到 2，意味着“跳一步之后，你有机会踩在下标 1 或 2 上”。

第二跳，遍历 i = 1 到 curEnd = 2。i = 1 时，nums[1] = 3，farthest 更新为 1 + 3 = 4。i = 2 时，nums[2] = 1，farthest 保持 4 不变。等 i 走到 2，i 等于 curEnd，再次跳一步，steps 变成 2，curEnd 更新为 4。此时 curEnd 已经等于数组最后一个下标 4，循环可以结束，返回 steps = 2。

注意一个细节：在 i = 1 时，farthest 已经更新到了终点 4，但 wei 不能立刻把 steps 加 1。一定要等到遍历指针走到当前覆盖区间的边界 curEnd = 2，这一“跳”的完整范围才能闭合。这也是很多人第一次写代码容易少算或者多算一个计数的地方。

我用一个字符图把这个过程画出来：

下标: 0 1 2 3 4 nums: [2] [3] [1] [1] [4] 第一跳前: [起点] 0 覆盖区间: [0, 0] 第一跳后: 0 1 2 [---------] 覆盖区间: [0, 2] 第二跳过程中: 从下标1看: 1+3=4，终点可见 从下标2看: 2+1=3，不如4 走到2边界，跳跃次数+1，区间更新为[0, 4] 第二跳结束: 0 1 2 3 4 [-------------------] 到达终点

这个图比文字直白多了。面试的时候如果能快速画出这样的区间推进图，会比干讲代码有说服力得多。

3.3 图解过程的收敛性验证

再看一个连续小步的例子 nums = [1, 1, 1, 1]，验证算法不会“贪过头”。

初始化：steps = 0，curEnd = 0，farthest = 0。 i = 0：farthest = max(0, 0 + 1) = 1。i == curEnd，steps = 1，curEnd = 1。 i = 1：farthest = max(1, 1 + 1) = 2。i == curEnd，steps = 2，curEnd = 2。 i = 2：farthest = max(2, 2 + 1) = 3。i == curEnd，steps = 3，curEnd = 3。 循环条件 i < n - 1，n = 4，所以 i 最大到 2。返回 steps = 3。

从下标 0 到下标 3，每一步只能跳 1 格，最优步数就是 3，和贪心结果一致。

再看一个“最后一跳前就发现终点”的例子 nums = [1, 2, 3]。初始化后： i = 0：farthest = 1，i == curEnd，steps = 1，curEnd = 1。 i = 1：farthest = max(1, 1 + 2) = 3，已经覆盖终点。因为 i = 1 到 curEnd = 1，steps = 2，curEnd = 3，此时 curEnd >= 2，break。返回 steps = 2。

如果漏掉 break，继续遍历 i = 2，会发现 i == curEnd 又执行一次 steps++，结果变成 3，这就是一个经典的“多跳一次”的 bug 来源。我会在代码部分专门讲怎么避开。

4. 代码实现与边界细节

4.1 Java 实现

用 Java 写核心逻辑，我建议直接背这种写法，它把所有边界都处理得比较干净：

class Solution { public int jump(int[] nums) { int n = nums.length; if (n <= 1) { return 0; } int steps = 0; int curEnd = 0; int farthest = 0; for (int i = 0; i < n - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i == curEnd) { steps++; curEnd = farthest; if (curEnd >= n - 1) { break; } } } return steps; } }

这里我最想强调的点在 for 循环条件：i < n - 1。为什么不遍历最后一个位置？因为当 i 走到倒数第二个位置时，如果已经触发了 steps 增加，并且 curEnd 更新后指向终点，循环就可以结束；如果还没有触发，说明最后一个位置不需要作为“起点”被考虑，它只是终点。要是把循环写成 i < n，当这个位置上恰好 i == curEnd 时，会再多算一次跳跃，返回结果就偏大。

4.2 Python 实现

Python 版本逻辑完全一致，只是语法更短一些：

from typing import List class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) if n <= 1: return 0 steps = 0 cur_end = 0 farthest = 0 for i in range(n - 1): farthest = max(farthest, i + nums[i]) if i == cur_end: steps += 1 cur_end = farthest if cur_end >= n - 1: break return steps

这段代码我在本地跑过大量测试用例，包括全 1 数组、跳跃值很大的数组、长度 1 的数组，都能稳定返回正确结果。Python 写算法题的优势是表达力强，但要注意 range(n - 1) 这个边界，别顺手写成 range(n)。

4.3 几个容易写错的边界细节

第一个是 n <= 1 直接返回 0。有些人会漏掉长度为 1 的情况，导致循环里 i = 0，i == curEnd，steps 变成 1，返回错误结果。题目里 nums 长度至少为 1，所以这个判断必须有。

第二个是“更新 farthest 的时机”。一定要在进入循环后立刻更新当前 i 的最远覆盖，再判断是否到达 curEnd。顺序反了会漏掉当前点的贡献。比如在 i 恰好等于 curEnd 时，你先 steps++ 再更新 farthest，那这个点本身能跳多远就没算进去。但同时要注意，即使顺序是对的，当 i 到达 curEnd 时，当前点的跳跃潜力已经计入 farthest 了，所以可以放心更新 curEnd。

第三个是 break 条件。我这版代码在 curEnd >= n - 1 时 break，因为我们已经能确保覆盖终点，不需要继续循环。如果你不 break，只是让它自动循环完，在部分情况下也可能得到正确结果，但多跑空转没有意义。更重要的是，某些变体写法里如果不 break，会让步骤多算一次，所以 break 是一个双保险。

提示：我见过很多题解把 curEnd 命名为 end，把 farthest 命名为 maxPos。理解成“当前这个区间的最远点”和“下一区间的最远点”就好，变量名不重要，语义别混。

5. 复杂度分析与范围延展

5.1 实战复杂度 vs 暴力复杂度

这个贪心算法的时间复杂度是 O(n)，空间复杂度是 O(1)。为什么 O(n) 一定够？因为数组每个下标最多被遍历一次，每个位置只会触发一次“到达边界并更新区间”的操作。你可能会疑惑：每跳一次不就要重新遍历区间吗？是，但你注意，这个区间是连续的，是从前向后推进的，不会回头重新扫描。所以总遍历次数就是数组长度，线性复杂度。

对比一下暴力思路：如果每次从当前位置枚举所有可达点，选择下一个位置，再继续枚举，最坏情况下每个点位都可能枚举 O(n) 个后续点，复杂度是 O(n^2)。当数组长度到 10^5 级别，O(n^2) 基本会超时。这也是面试官为什么看重这道题：他能从你的复杂度分析判断你是在“背答案”还是真的理解了贪心。

空间上除了几个变量什么都没存，不可能更优了。这题做到 O(n) 时间 + O(1) 空间，就是理论最优解。

5.2 面试常问的变体：输出跳跃路径

如果你掌握了贪心区间法，面试官可能还会追问一个进阶问题：如果不仅要返回最小步数，还要输出具体的跳跃路径，应该怎么做？

一个常见做法是从终点反向贪心。从最后一个位置开始，每次在数组左侧找到“能一步跳到当前目标位置”的最远下标，作为路径中的上一个落脚点，然后把这个下标作为新的目标，继续向前找。因为前面贪心算法保证了最小步数，所以反向找出来的路径长度也一定是最小步数。

具体来说，假设目标是 target，初始 target = n - 1。从 i = 0 开始向左扫描，找第一个满足 i + nums[i] >= target 的位置，把这个位置记录到路径，然后把 target 更新为 i，继续重复。扫描过程中不需要额外数组，只记录路径即可。这个反向方法的正确性在于：区间贪心保证每一步覆盖范围最大化，反向过程会自然地收敛到最左侧的必要跳点。

5.3 同类思想还能用到哪

“维护边界 + 逐步扩大覆盖区间”这种思路，在算法题里非常通用。LeetCode 55 跳跃游戏 I 本质就是同一模型的简化版；还有一些区间合并、最少喷头灌溉、最少会议室等题目，背后都是“当前覆盖范围 + 贪心扩展”的套路。

我做这类题的经验是：一旦看到“最少的次数/个数”“覆盖一个区间”这样的关键词，先想想能不能用双指针或者边界扩展。如果能证明局部最优可以推出全局最优，通常就是贪心；如果局部最优会有后效性，再考虑 DP。这个判断过程，比单纯记题型更重要。

6. 常见错误与排查实录

6.1 高频错误：把“当前可跳最远位置”当作“下一跳落点”

刷题群里经常有人问：为什么我用了“每次跳最远”的贪心，结果不对？这里必须把概念掰扯清楚：贪心算法确实用了“最远”这个数字，但用的是“区间内所有点的最远覆盖”，而不是“某个具体起跳点自己跳的最远”。

换句话说，我们不是选择下标 A 作为落点，而是承认“当前这一步的落脚点可以是区间内任意一点，只要这一步结束后，下一步覆盖范围最远”。这个区别用代码看最清楚：代码里没有记录任何“我选择落在下标几”的变量。我们只维护了 curEnd 和 farthest。这就是区间覆盖贪心和点贪心的本质区别。

6.2 问题速查表

我整理了一份常见问题速查表，方便你排查自己代码的思路：

这张表是我自己刷题、也帮别人 review 代码时总结出来的。你会发现，绝大多数错误都不是贪心方向有错，而是边界条件写错或者对“farthest”的理解出了偏差。

6.3 给刷题新手的几点心得

我见过不少人刷这道题，第一遍看题解觉得“恍然大悟”，关上答案自己写又卡住。我的建议是：不要急着背代码，先在草稿纸上画 3 个用例的覆盖区间推进过程，再手写一遍代码。只要你能解释清楚“为什么 i == curEnd 时步数加一”，你已经掌握了贪心里最核心的“区间边界闭合”思想。

画图的时候，把 curEnd 标成一条竖线，把 farthest 标成一个向右延伸的箭头。当遍历指针碰到竖线，就把竖线推到箭头的位置，步数加一。你重复画几个用例，自然能理解为什么这是个 O(n) 的算法。

另外，刷完这道题之后，我强烈建议立刻做跳跃游戏 I，两道题对比着看。前者是后者的简化版，只问能否到达。你会发现，跳跃游戏 I 只要维护一个 farthest 并实时更新即可，连步数都不需要。把两道题连起来做，贪心的“区间覆盖”模型会记得很牢。

实操心得：这道题在面试里出现频率不低，我建议不只准备解法，还要准备“为什么贪心是正确的”这句话。你可以这样说：每一步都让覆盖区间尽可能向右扩展，最优路径中的所有跳跃点必定被包含在每一层的最大覆盖区间里，因此区间扩展的层数就是最小跳跃次数。

这道题对我来说最大的价值，是把“贪心就是局部最优等于全局最优”这句话落地成了一个具体模型。它不是那种靠反例才能说服你的玄学贪心，而是每一步都直观可见的区间推进。如果你现在刷它有点吃力，别急，像我一样重新从覆盖区间的角度理解一遍，再动手写代码，基本就能稳住了。