看到LeetCode热题100里的45题跳跃游戏II很多人的第一反应是“这不就是跳跃游戏I的升级版吗”确实题目只多了一个“最少跳跃次数”的要求但难度直接从中等偏易变成了中等偏难。这道题在面试中出现的频率极高尤其适合考察候选人对贪心思想的理解到底停留在“背模板”还是“真的想明白了”。先说结论这道题的最优解是O(n)时间、O(1)空间的贪心代码核心不到二十行但真正难的不是写代码而是理解“步数为什么在curEnd边界才增加”这个设计。这篇文章我会从题意拆解、贪心推导、代码逐行解析、常见坑点四个层面完整过一遍。无论你是刚开始刷热题100的新手还是准备面试想快速回顾经典题的老手这篇都值得花十分钟读完。1. 先读懂题目到底在求什么1.1 输入输出与跳跃规则题目给定一个非负整数数组nums你最初位于数组的第一个下标数组中的每个元素代表你在该位置可以跳跃的最大长度。目标是用最少的跳跃次数到达数组的最后一个位置题目保证输入一定可以到达末尾。举个例子nums [2,3,1,1,4]。从下标0出发nums[0] 2表示你可以跳到下标1或下标2。一种走法是0 - 1 - 4需要两跳另一种走法是0 - 2 - 3 - 4需要三跳。题目要求返回的就是最优方案下的跳跃次数这里答案是2。这里有一个容易混淆的细节“代表最大跳跃长度”意味着你从当前位置i可以跳到任意满足 i j i nums[i] 的下标j而不是必须精确跳到 i nums[i]。很多刚接触这道题的人会把“最大”理解成“唯一”这种误解是后面所有错误解法的源头。1.2 和跳跃游戏I只差一个“最少次数”LeetCode 55题跳跃游戏I是本题的姊妹题它只问你“能不能跳到末尾”返回一个布尔值。55题的核心思路非常简单维护一个当前能覆盖的最远下标然后遍历数组不断更新这个覆盖范围如果覆盖范围能到达或超过n-1就返回true。到了45题题面好像只是把“能不能”换成了“最少要几次”很多人的第一反应是“我沿用55题的思路顺便计个数不就行了吗”实测下来这个直觉是错的。因为55题只判断可达性你不需要关心具体选择哪条路径只要覆盖范围能覆盖到终点即可。但45题要求“最少次数”同样一个覆盖范围内不同的路径选择会导致后续覆盖能力完全不同。举个例子如果只按55题的思路从头到尾更新一次覆盖范围你得到的是“经过无限次跳跃后最远能到哪”而不是“用最少次数到达终点”。也就是说55题把所有跳跃当成一个整体来看而45题必须把跳跃切成“每一段覆盖范围”来统计。1.3 “最少次数”不等于“每次都选最远”这是大多数人踩的第一个思维陷阱。凭直觉想既然要少跳那我每次跳得最远不就行了吗我们来验证这个想法nums [2,3,1,1,4]。按“每次都跳最远”的逻辑从下标0跳最远到下标2nums[0]2下标2的值是1只能跳到下标3下标3的值是1再跳到下标4总共需要3跳。但最优解是2跳先跳到下标1因为nums[1]3可以直接跳到下标4。为什么“每次跳最远”会失败因为第一跳选得远不代表下一跳能接续得更远。跳跃问题里真正影响全局的是“每个位置能提供的后续覆盖能力”而这个能力并不是由当前位置的数值单独决定的而是由“你能到达的所有位置中下一步能延伸到的最远下标”决定的。所以这道题的贪心单位不是“某个具体落脚点”而是“每一跳的可达范围”。每次选择跳跃时我们看的不是“这次跳到哪”而是“这次跳跃之后下一跳最远能扩到哪里”。2. 贪心解法用“边界”管理步数2.1 覆盖范围的滚动更新理解了上面那个陷阱贪心思路就变得自然了。我们把整个跳跃过程看成一段一段的区间推进。定义当前已经使用的跳跃次数对应的“覆盖边界”为curEnd表示当前这一跳最多能到达的下标。初始时在起点位置curEnd 0跳跃次数ans 0因为还没开始跳。然后定义nextEnd表示从当前这一段覆盖范围内任意一个位置出发再进行一跳后能到达的最远下标。每遍历到一个位置i就尝试更新 nextEnd max(nextEnd, i nums[i])。注意这里i nums[i]表示从i出发能到的最远位置。当遍历到i curEnd的时候说明当前这一段覆盖范围已经全部走完了你被迫必须再跳一次才能继续向更远处前进。此时把curEnd更新为nextEnd同时ans加一。一直循环到遍历完倒数第二个位置返回ans。因为最后一个位置已经是终点不需要再跳。2.2 为什么边界一到就必须结算这个“i curEnd才加一”的设计是整道题正确性的核心。我用一个生活化的类比来解释假设你在玩跳跳棋当前步数能走的范围是地面上画好的一个圈圈内所有格子你都能用“一步”到达。你站在圈里的任意位置都可以观察圈外哪个格子离你最近、走一步能蹿到多远。当你把这个圈逛完了发现步数不增加就无法去更远的格子于是你必须迈出新的一步此时新的圈子就是你刚刚观察到的“最远下一步能到的地方”。在代码里curEnd就是这个圈子的边界。i遍历到边界意味着“当前步数可以到达的所有位置”已经全部处理完下一步要想继续前进只能增加步数。这个“结算动作”本质上是在回答从已经覆盖的所有位置出发最远能再延伸到哪把下一次的边界设为这个最远值继续这个循环。正确的贪心思路总结成一句话就是在当前跳跃可达的范围内选择下一次跳跃能到达的最远位置。这句话里的“当前跳跃可达范围”和“下一次跳跃能到达的最远位置”都是区间层面的概念而不是单独某一个下标。2.3 三个变量的分工为了帮助记忆我把三个核心变量的作用整理成一张对照表变量名含义更新时机curEnd当前这一跳能覆盖的右边界初始为0每次i curEnd时更新为nextEndnextEnd从当前覆盖范围内任意位置出发下一跳能到达的最远下标每遍历一个i就尝试取max(i nums[i])ans累计跳跃次数初始为0每次i curEnd时加1这里有个很多文章没点透的细节nextEnd是“当前覆盖范围内所有可能落脚点”能延伸出的最远距离而不是从某个具体点延伸出的距离。计算nextEnd时它其实已经聚合了当前这一跳覆盖范围内所有位置的信息。当curEnd位置到达时nextEnd已经是一个全局最优的扩展结果所以此时更新curEnd是安全的、不会错过任何更优路线。我建议你拿到这道题以后先别看代码自己在纸上用[2,3,1,1,4]推演一遍这个流程把每一步的i、curEnd、nextEnd、ans写出来比直接抄代码有效得多。3. 代码实现与逐行解析3.1 Java完整代码下面给出Java版本的标准贪心实现带有逐行注释。class Solution { public int jump(int[] nums) { int n nums.length; if (n 1) { return 0; // 已经在终点不需要跳 } int curEnd 0; // 当前跳跃次数的可达右边界 int nextEnd 0; // 当前覆盖范围内下一跳能到达的最远下标 int ans 0; // 累计跳跃次数 // 为什么是 n-1因为最后一个位置不需要再发起跳跃 for (int i 0; i n - 1; i) { // 更新从当前点出发能到达的最远距离 nextEnd Math.max(nextEnd, i nums[i]); // 到达当前这一跳的边界必须增加一跳 if (i curEnd) { ans; curEnd nextEnd; // 如果当前边界已经覆盖到终点附近可以提前结束 if (curEnd n - 1) { break; } } } return ans; } }这段代码的时间复杂度是O(n)空间复杂度是O(1)。遍历了一遍数组没有任何额外的数据结构可以说是这道题的最优形态。3.2 三个容易被忽视的细节第一个细节循环条件是i n - 1而不是i n。因为终点本身不需要再跳。如果你把循环写成i n在最后一个位置i n-1时如果此时i curEnd会再多加一次跳跃次数导致结果偏大。一个安全的写法是在循环内判断 if (i n - 1) break但我个人更推荐直接把循环上限定为n-1从这个层面杜绝误判。第二个细节中间有一段curEnd nextEnd之后我加了一个if (curEnd n - 1)的判断。这不是必需条件但能提升一点效率。因为当你发现当前已经能覆盖到终点时后面的遍历就没有意义了可以提前退出。需要注意的是break之前ans已经正确加过一因为curEnd到达终点的那一跳在位置i curEnd时已经结算了。第三个细节nums长度为1的情况。题目说“你最初位于数组的第一个下标”如果数组中只有一个元素那么你已经位于终点返回0即可。很多初写者会漏掉这个边界导致连[0]这种输入都过不了。顺带一提即使nums[0] 0且数组长度为1也是合法情况因为你人已经在终点了。3.3 边界与特殊输入的应对除了单元素数组还有两类输入值得注意。第一类是“起点就能直接覆盖到终点”的情况比如nums [5, 1, 1, 1, 1]。遍历到i 0时nextEnd被更新为5已大于等于n-1但此时i ! curEndcurEnd还是0所以不会立即结算。接着i遇到curEnd边界时ans加一然后curEnd更新为5curEnd n-1成立break。最终返回1一次跳跃即可。这个流程是正确的因为从起点可以直接跳到终点。第二类是数组中间有0但不影响可达性的情况比如nums [1, 0, 2, 1]。从0跳到1位置1无法移动但位置2在位置0的覆盖范围内吗不在因为nums[0] 1只覆盖到下标1。这种情况下实际无法到达终点但题目保证可达所以这类输入不会出现。不过面试官如果追问“如果题目不保证可达怎么办”你就需要在循环里加一个判断当i curEnd且nextEnd curEnd时说明被困住了无法再前进此时应该返回-1或根据题目要求处理。4. 常见问题与排查技巧实录4.1 为什么不是每次更新都加一这是评论区最常见的疑问“我每次都用max更新了nextEnd为什么不在更新nextEnd的时候顺便把ans加一”原因很简单更新nextEnd只代表“从某个位置出发能跳得更远”但这一步不一定需要付出一次新的跳跃。因为当前还在curEnd覆盖范围内跳跃次数并没有增加。比如[2, 3, 1, 1, 4]当i 0时nextEnd 2当i 1时nextEnd 4。但此时ans仍然是0因为你还没有真正跳过你还在起点到curEnd0的范围内。如果把ans加在这里就会把“潜在的最远距离”和“已经发生的跳跃”混为一谈。可以这样理解nextEnd是“未来的潜力值”curEnd是“已经兑现的现实边界”。只有当前现实边界被遍历完才需要把未来的潜力兑现成新的一次跳跃。4.2 遍历到n-1会差在哪里我见过很多解法在for循环里使用i n然后在循环内部判断if (i n - 1) break。这种写法也能过但容易在边界判断上出错。更隐蔽的错误是没有break直接让i遍历到n-1导致多算一次。我们来推演nums [1, 2, 3]期望答案是2。如果用i n的循环不设breaki 0nextEnd 1i curEnd(0)ans 1curEnd 1。i 1nextEnd 3i curEnd(1)ans 2curEnd 3。i 2nextEnd 5i curEnd(2)ans 3curEnd 5。 返回3错误。问题出在i 2时你已经站在终点根本不需要再跳。你用i n-1的写法循环在i 1就结束了返回2完美避开了这个坑。4.3 如果nums里有0到底该怎么办虽然题目说输入保证可达但面试官经常会借这个点延伸提问。核心判断标准是当i curEnd且nextEnd curEnd时说明当前覆盖范围耗尽但没有任何位置能产生更远的覆盖也就是卡死了。此时应返回-1或执行附加逻辑。这个判断要放在结算分支内部因为只有走到边界才需要“检查是不是卡住”。如果在非边界位置判断可能误杀一些还没遍历完的潜在覆盖点。4.4 换个角度这题本质上是BFS很多人学这道题时死记“贪心”但没意识到这题其实也可以用BFS理解。我们把数组想象成一个图每个节点i可以连到i1到inums[i]之间的所有节点。求起点到终点的最短路径直觉上就是BFS。标准BFS的时间复杂度是O(n^2)因为最坏情况下每个点可以扩展O(n)条边。贪心解法本质上是BFS的高度优化版本它不再维护队列里的每个节点而是只在每一层每一次跳跃记录“这一层能扩展出的最右边界”。反正目的是覆盖到终点那我只关心最右边界即可队列里那些无法产生更远扩展的点根本不用处理。这就是为什么能把O(n^2)的BFS优化成O(n)的贪心。面试时如果能把这一层理解讲清楚往往能让面试官眼前一亮。很多候选人只会背代码被问到“为什么贪心是对的”就卡壳但只要搬出BFS的分层视角再结合“每一层不用全部节点只需要最远边界”这句话说服力就强很多。5. 进阶思考与变体启发5.1 为什么动态规划不是最优解不少教材会先讲动态规划解法dp[i]表示跳到i所需的最少步数从0到i遍历所有能到i的前驱位置j如果j nums[j] i则dp[i] min(dp[i], dp[j] 1)。时间复杂度O(n^2)空间O(n)。这个解法正确且容易想到但在这道题里是次优解。原因在于状态的转移中存在大量冗余dp[j]相同的所有前驱j对dp[i]的贡献完全一样没必要逐个比较。贪心解法把“哪个j的后续能力更强”这件事压缩成了一个nextEnd变量省去了所有无效排列组合。这里可以形成一个选题经验当状态转移方程里存在“取最小值”且值域很小或可合并时要留意是否存在贪心或前缀最优之类的优化空间。当然动态规划作为兜底思路仍然值得掌握至少它能在你一时想不出贪心时保证通过。5.2 如何快速验证自己的实现是对的刷题之后别急着提交先用几组边界数据自测比连续提交红绿灯快得多。我常用的测试用例可以按以下分类整理测试输入期望输出验证点[0]0单元素数组[2, 1]1一步直达[2, 3, 1, 1, 4]2标准最优跳法[1, 2, 3]2防止遍历到n-1多算一次[2, 0, 0, 0]-题目保证可达但自测时观察是否卡死[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0]2大跨度跳跃后仍需补跳这些用例基本覆盖了单元素、直接覆盖、分段推进、陷阱位置等情况。跑完自测再提交一次过的概率会高很多。5.3 从跳跃游戏到区间类问题的迁移45题想通以后再看LeetCode 55题跳跃游戏I会轻松不少。进一步地热题100里还有56题合并区间、57题插入区间这类区间覆盖题目它们的核心都是维护一个“右边界”并不断吞噬更大的范围。这种“维护覆盖右边界贪心推进”的思维模型在真实业务里的调度问题、资源分配问题中也很常见。我个人建议的做法是把55题、45题和56题放在同一天刷刷完做一个小总结把它们的核心变量、更新时机画在同一张表里。你会发现它们本质上都是“遍历一次维护一个最大右边界”的变体。这种横向对比的记忆效果远好于单纯刷题。最后再分享一点我自己的实际体验。这道题我前后给不下十个候选人讲过发现最容易出问题的不是代码实现而是“为什么i curEnd才加一跳”这个时机。很多人写的时候凭感觉觉得“该加了就加”一旦被追问就露馅。我的建议是遇到这种边界结算型贪心一定自己把变量推进过程在纸上完整画一轮画到能不看代码重述出每一步为止。这个功夫花不了十分钟但对理解深度的影响是决定性的。以后再做类似的区间覆盖题、任务调度题你也会比那些只背模板的人多一分底气。