LeetCode 45. Jump Game II 这道题是我在刷题群里见过“AC 了但没懂”比例最高的一题。很多读者看完三五行题解代码抄一遍过了转头问“end 到底代表什么”“farthest 为什么能直接覆盖末尾”结果没人能讲清。这篇题解我想把从题意到贪心再到两种写法和边界陷阱的完整链路拆开来讲。目标读者大概是两类刚开始刷贪心/数组题的朋友以及已经 AC 但想搞清楚原理、准备面试讲证明的朋友。先说结论这道题的最优解法是 O(n) 时间、O(1) 空间的贪心核心思路不是“每次跳最远”而是用 BFS 分层的方式维护“这一步能到达的最远边界”和“下一步能到达的最远边界”。这个思路一旦建立代码只有几行也不会再怕面试变体。1. 题目到底在问什么先别急着写代码1.1 从输入输出看题目的约束给你一个非负整数数组nums你最初位于数组的第一个下标0。数组中的每个元素代表你在该位置可以跳跃的最大长度。也就是说站在下标i时你可以跳到[i 1, i nums[i]]范围内的任意一个位置上。你的任务是到达最后一个下标返回最少需要跳跃多少次。题目保证输入总是可以到达最后一个位置。看到这一堆文字先别急着想算法。我们先用一个例子把题意落地。假设nums [2, 3, 1, 1, 4]从下标 0 出发nums[0] 2所以你可以跳到下标 1 或下标 2。如果跳到下标 1这里nums[1] 3可以继续跳到下标 2、3、4其中 4 就是终点所以总步数是 2。如果第一步跳到下标 2这里nums[2] 1只能到下标 3再从下标 3 走一步到下标 4总步数就变成了 3。所以答案是 2。这个例子同时也是一个很好的反直觉案例第一步选择“看起来最远”的下标 2反而导致整体变慢。1.2 这题和 Jump Game I 的核心差异很多人在做这道题之前已经刷过 LeetCode 55 Jump Game那道题只问“能不能到达终点”。它的经典做法是维护一个最远可达距离maxReach遍历过程中不断更新只要maxReach n - 1就说明可以到达。为什么那道题只需要一个变量因为只判断可行性不管步数也不需要知道“当前走的是第几步”。你只管把跳跃范围像滚雪球一样滚大能覆盖到终点就成功。Jump Game II 多了一个“最少步数”事情就变了。你不能只知道“最远能到哪”还必须知道“这是第几步的边界”以及“下一步最远能到哪”。直观理解是把跳跃过程想象成一层一层向外扩张第 0 步只能覆盖位置 0从位置 0 出发能到达的所有位置构成第 1 步的覆盖范围再从这一层所有位置出发能到达的更大范围是第 2 步的覆盖范围。这个结构本质上就是 BFS 的分层只不过这里允许跳到的范围是一个连续区间所以可以用几个变量在遍历中隐式完成 BFS而不需要显式建图。从 Jump Game I 到 Jump Game II最大的思维升级就是不要把目光盯在“当前这一步跳到哪个点”而要把目光放在“当前这一步覆盖的区间能扩展到哪里”。理解了这一点后面的贪心写法就顺理成章了。2. 为什么“每次跳最远”不是正解贪心策略的误区与修正2.1 一个反直觉的例子我第一次做这道题的时候第一反应是“每次跳最远不就完了吗”然后立刻被nums [2, 3, 1, 1, 4]打脸。如果每次跳最远从下标 0 跳到下标 2nums[2] 1只能到下标 3再走一步到下标 4总共 3 步。但最优解只要 2 步理由是第一步先跳到下标 1虽然这一跳本身距离更短但它把下一步的“射程”拉大了。为什么会这样因为跳跃问题里一步的“效益”不是由这一步跳了多远决定的而是由这一步降落后从落点还能再延伸多远决定的。你可以把每个位置看成一张跳板跳板的长度是nums[i]而跳板的位置决定了它的“覆盖半径”。第一次跳到距离更近但更长的跳板上比跳到距离更远但很短的跳板上更划算。所以“每次跳最远”只是在优化单一维度的目标忽略了跳板自身的长度自然不是正解。2.2 正确的贪心视角把跳跃看成 BFS 分层想通之后我把问题换了一种看法假设你现在处于“第 k 步”那么你能够到达的所有位置是一个区间[0, end]。你的目标不是在这一步里“跳到一个好看的中间点”而是从[0, end]中所有位置出发计算出下一步最远能延伸到哪。这个“下一步最远能到哪”就是farthest。当你把这个区间[0, end]中的所有位置都遍历完之后说明无论你怎样选择第 k 步能做的已经做完了。下一步必须从某个已经到达的位置出发而所有出发点的最大延伸就是farthest。于是步数加 1把end更新成farthest。这就是一个标准的 BFS 分层过程第 0 层只有位置 0end 0。遍历位置 0算出farthest max(farthest, 0 nums[0])。到达i end时步数加 1新边界等于farthest。继续遍历第 1 层内的所有位置继续更新farthest直到再次i end。这个过程中我们并没有具体记录“从哪个点跳到了哪个点”因为题目只要步数不需要路径。这种只看边界不看内部具体路径的贪心才是这道题的正确打开方式。3. 标准解法一BFS 分层 单次遍历O(n) 时间、O(1) 空间3.1 两个变量加一个步数计数器的循环不变量最优解只需要三个变量steps当前已经使用的跳跃次数。end用steps步能够到达的最远下标。换句话说这是当前层的右边界。farthest在遍历当前层的过程中从这一层所有位置出发下一步能够到达的最远下标。循环遍历下标i范围是0到n - 2。为什么最后一个位置不遍历因为最后一个位置已经是终点不需要再从它往外跳。如果强行遍历到n - 1可能会在i end时多做一次无意义的跳跃导致答案加 1。每遍历一个位置先执行farthest max(farthest, i nums[i])这表示从当前位置出发最远能跳到i nums[i]用它来扩展下一层的边界。然后判断if i end: steps 1 end farthest这里i end的含义是当前层已经扫描完最后一个位置。不管接下来跳到哪都必须把步数加 1并把边界推进到farthest。这个更新顺序不能反过来否则当前位置i的扩展能力还没有被计入farthest会少算一段距离。3.2 代码实现Pythonclass Solution: def jump(self, nums: List[int]) - int: n len(nums) steps 0 end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i end: steps 1 end farthest if end n - 1: break return stepsCclass Solution { public: int jump(vectorint nums) { int n nums.size(); int steps 0, end 0, farthest 0; for (int i 0; i n - 1; i) { farthest max(farthest, i nums[i]); if (i end) { steps; end farthest; if (end n - 1) break; } } return steps; } };Javaclass Solution { public int jump(int[] nums) { int n nums.length; int steps 0, end 0, farthest 0; for (int i 0; i n - 1; i) { farthest Math.max(farthest, i nums[i]); if (i end) { steps; end farthest; if (end n - 1) break; } } return steps; } }很多题解里没有break只靠range(n - 1)限制循环结束这样也是对的。加上break是提前结束防止end已经覆盖末尾后还继续扫描属于可选的微优化。我习惯加上因为面对超长数组时可以减少无意义遍历代码逻辑也更明确。3.3 正确性证明思路为什么这样贪心不会漏解贪心题最怕的不是写不出来而是写完不确定对不对。这里我给一个面试也能直接讲的证明思路用归纳法。初始时steps 0end 0显然用 0 步可以覆盖的位置集合是[0, 0]。假设当前已经用k步覆盖了[0, end]并且[0, end]中每个位置都在遍历中被访问过。访问过程中我们计算了从这些位置出发能到达的最远位置记为farthest。那么从[0, end]中任意一个位置出发再跳一步能到达的最远位置都不可能超过farthest。也就是说用k 1步能覆盖的最大范围是[0, farthest]。因此当i走到end时把steps加 1把end更新为farthest得到的正是“用更少步数不可能达到、用当前步数一定可以达到”的边界。由于每层边界都在单调右移最终必然覆盖到n - 1此时步数就是最小步数。这个证明的关键在于我们不是在模拟某一条具体路径而是在计算“所有可能路径中这一层往外扩展的极限”。因为只需要最少步数极限就足够了。4. 标准解法二从终点反向贪心另一种思路4.1 从终点往前找“最靠左的起跳点”如果正向贪心的分层思想让你觉得抽象可以换个方向思考。我们站在终点n - 1往前看想用一步到达终点需要找一个位置i满足i nums[i] n - 1。为了让总步数更少我们希望这个位置尽量靠左因为位置越靠左说明前面的剩余路程越短后续需要的步数越少。所以反向贪心的做法是从终点位置开始每次都从下标 0 从左往右找第一个能跳到当前目标位置的点把这个点作为新的目标步数加 1。重复这个过程直到目标变成起点 0。为什么要找“从左往右第一个”而不是“从右往左第一个”举个例子nums [2, 3, 1, 1, 4]目标终点是 4。从左往右看下标 0 跳不到 4下标 1 能跳到 4所以上一步的起点选下标 1。这个选择把目标从 4 移到了 1然后下一步从起点 0 可以直接跳到 1。整个过程只需要 2 步。如果从右往左找“第一个能跳到的点”可能会找到下标 3因为nums[3] 1也能到 4但把目标设为 3 之后前面还需要更多步数结果不是最优。这个写法的好处是思路非常符合直觉展开成代码也简单坏处是时间复杂度不理想。4.2 实现与复杂度对比反向贪心的代码def jump(nums): n len(nums) pos n - 1 steps 0 while pos 0: for i in range(pos): if i nums[i] pos: pos i steps 1 break return steps这个代码每次找到新目标后内层循环都重新从 0 开始扫描。如果数组是[1, 1, 1, ..., 1]每次只能把目标往前挪一格总操作次数大约是n (n-1) (n-2) ...也就是 O(n^2)。在 LeetCode 45 的数据范围下Python 版本很容易超时所以它更适合作为思路层面的“另一种视角”而不是正式提交的首选方案。解法时间复杂度空间复杂度综合评价正向贪心 BFS 分层O(n)O(1)最优解推荐反向贪心O(n^2)O(1)思路清晰但大数组会超时动态规划O(n^2)O(n)可用于扩展问题比如统计方案数我在学习时会把反向贪心写在草稿纸上用它来验证自己对“步数递增”的理解但提交代码永远用正向贪心。面试时如果时间充裕可以先把反向贪心讲给面试官听再引出正向优化的动机这会显得你既有直觉又有优化意识。5. 边界情况、测试用例与常见实现坑5.1 最容易踩的坑end 和 farthest 的更新顺序这道题代码短但错误非常隐蔽。最常见的错误是把farthest max(farthest, i nums[i])放到if i end的后面。一旦顺序反了当i刚好等于当前层边界时当前位置本应作为当前层的一员去扩展下一层结果它的扩展能力根本没被算进farthest导致步数偏多。另一个容易犯的错误是在更新end时把farthest重置为 0。farthest是“当前层所有位置累计产生的下一层最远边界”是一个跨迭代累积的变量不是每个位置单独算完就清零的。一旦清零后面遍历到更远位置时farthest会丢失前面位置的信息结果完全错乱。还有一个小坑是循环边界的写法。有人写成for i in range(n)在i n - 1时如果恰好i end会多做一次跳跃。比如nums [1, 1]正确结果是 1但写成range(n)后会在i 1时触发steps 1最终返回 2。解决办法就是循环到n - 2为止或者在循环体内判断if i n - 1: break。5.2 一组值得先跑的测试用例我每次写完这道题代码都会跑下面这组用例输入期望输出说明[0]0已经站在终点不需要跳[2, 3, 1, 1, 4]2LeetCode 官方示例[2, 3, 0, 1, 4]2中间有 0 也能跳到终点[2, 0, 0]1起点一步直达终点[1, 1, 1, 1]3每一步只能往前挪一格[5, 4, 3, 2, 1, 0]1起点一步覆盖全部其中[2, 0, 0]最能检验你是否把循环边界写错。如果写成range(n)这个用例可能会在遍历到最后一个位置时把答案从 1 变成 2。[0]则检验你对长度为 1 的数组是否有防御性处理虽然range(n - 1)天然返回 0但如果你额外加了if n 1: return 0也没问题只是显得冗余。5.3 什么时候不要选贪心并不是所有“最少跳跃”类问题都能用这个贪心。一个简单判断标准是如果每一步的代价不恒定或者跳到一个位置后会产生额外收益/惩罚贪心就不一定成立。比如题目改成“每个位置有跳跃代价求最小代价到达终点”这就是带权最短路问题贪心的“只看最远边界”策略会失效应该用 Dijkstra 或 DP 类方法。同样如果要求输出所有最少步数的方案数单靠end和farthest也不够需要把状态细化到每个位置用 DP 统计。所以这道题适合作为贪心入门题但不要在没分析清楚代价模型时就把同一套模板套到所有跳跃问题上。6. 这题在面试中的考察方式与延伸变体6.1 面试官最常追问的四个问题我模拟过几轮面试发现面试官在 Jump Game II 之后至少会追问这么几个方向第一证明贪心正确性。按 3.3 的归纳法讲重点说清楚“每一步得到的是当前可达集合的最远边界而最终答案只依赖边界”。只要讲到这里面试官一般就会点头。第二如果要求输出具体跳跃路径怎么办。贪心本身只算了步数但要输出路径可以额外维护一个bestPos记录让farthest取得最大值的位置。当i end时这个bestPos就是上一跳应该真正落脚的中间点。因为可能存在多个位置都能让farthest等于同一个最远值所以路径不一定唯一但最少步数相同。第三如果题目不保证一定可达怎么办。可以先借 Jump Game I 的思路判断是否可达不可达返回-1可达再套贪心。其实正向贪心也能处理如果遍历过程中出现end i的情况说明当前步已经卡住直接返回不可达。不过标准 45 题已经保证可达这个处理只在变体里需要。第四如果nums长度到 10^7怎么处理。正向贪心依然 O(n) 可过因为空间 O(1)不会有内存压力。反向贪心就完全不行了。这也是为什么最优解值得认真掌握。6.2 相关题目与拓展方向做完这题我建议按顺序刷一组跳跃系列的题能帮你把同一种思维模型练扎实Jump Game只判可达一个maxReach变量即可。Jump Game III从起点向左右跳目标变为某类值需要 BFS/DFS。Jump Game IV同值位置可以互相传送需要把同值分组后用 BFS 最短路。45 的带权变体每个位置有跳跃成本求最小成本此时贪心失效需要 Dijkstra 或 DP。你会发现这些变体的核心都是“如何定义状态以及状态之间怎么转移”。45 题教给你的“按层扩张”的思维在 1345 这种看起来完全不同的题里也非常有用因为 BFS 本身就是按步数分层的。6.3 我的个人刷题建议这类“最少步数”题我现在的反射弧是这样的先看状态是否只是“位置”转移是否有连续性以及目标是否只看到达性。如果都满足就优先尝试贪心如果状态里面有明显的“代价累计”就转 DP 或最短路算法。这个反射弧不是背出来的是靠多做几道跳跃系列题练出来的。最后再分享一个小技巧写这道题的代码时尽可能把所有变量名写得语义化比如end不要写成efarthest不要写成f。虽然代码看起来长了但在面试中讲思路时变量名本身就是注释能帮你和面试官保持在同一频道上。我见过不少候选人代码逻辑没错但因为变量命名太随意讲到end和farthest时自己都绕晕最后反而被扣分。LeetCode 45 的核心价值不是那几行答案而是让你真正理解“边界扩张”和“分层推进”这两个高级思想理解了它们跳跃系列的其他题都会变得简单很多。