1. 题目到底在问什么最小步数是“跳”出来的不是“算”出来的看到“跳跃游戏2”这个标题刷过题的朋友基本都会心一笑这是LeetCode 45题也是leecode100高频题单里绕不开的一道经典。第一次接触“最小跳跃次数”这六个字大多数人第一反应是动态规划——毕竟“最小XX”四个字天然带着DP的味道状态转移方程推一推样例跑一跑好像也能过。但如果你真的拿DP去解这道题等你把O(n^2)的代码写完再看到评论区那个一行扫描的贪心解法会觉得自己像个傻子。这道题的意思本身不复杂给你一个非负整数数组nums你一开始站在下标0的位置。数组里每个数字代表你在该位置最多能往前跳多少步比如nums[2] 3意思是你站在下标2时最多可以跳到下标5也可以只跳1步到下标3或者跳2步到下标4。目标是从下标0跳到最后一位问你最少需要跳几次。注意这里不是说只能跳到恰好等于位置值的地方“最多”两个字很关键。也就是说当前位置可以覆盖一段连续的区间你可以在这个区间里任意选择落脚点。题目保证了一定能跳到最后一位我后面会专门说这个“保证”有多重要所以你不需要处理“到不了”的情况只需要求最小次数。举个例子nums [2, 3, 1, 1, 4]。从0出发可以跳1步到下标1也可以跳2步到下标2。如果先跳到下标2这一步跳最远然后从下标2最多只能跳1步到下标3再从下标3跳1步到终点下标4一共3次。但最优解是先从0跳到下标1因为下标1的值是3直接一步跳到终点总共只需要2次。这个例子特别有杀伤力它直接干掉了一种很自然的错误思路——“每次都跳最远”。你想如果每一步都贪心地跳最远第一步跳到下标2结果反而绕远了。这就是为什么“跳跃游戏2”值得单独讲它教会你的不只是一道题而是贪心算法里一个极其重要的思想贪的不是眼前这一步的远近而是下一步的可达范围。这道题适合谁来学如果你在准备大厂算法面试、刷leecode100作为题库或者刚开始接触贪心算法想找几个经典案例练手这道题都值得你花半小时彻底搞懂。它的代码短到只有几行但里面的边界处理和贪心证明逻辑能把一个“感觉自己会贪心”的人打回原形。2. 贪心算法的选型思考从“跳得远”到“覆盖得远”2.1 常见的错误贪心每一步都跳最远先说说那道错误答案为什么错因为很多人第一眼就会踩进去。如果把问题简化成“当前能跳多远就跳多远”直觉上会觉得每次消耗最少的步数就能覆盖最大的距离那总步数不是最少吗这个直觉只对了一部分。问题在于你当前这一步跳得远并不代表你下一步还能跳得远。跳跃能力是跟着你的“脚下位置”走的而不是跟着你“已经走过的距离”走的。[2, 3, 1, 1, 4]这个例子就是最好的反例。从0开始能跳2步最远到下标2。你以为你赚了结果下标2的值只有1你下一步最远只能到3然后还得再跳一次到4。而如果你没跳那么远而是跳到下标1虽然这一步只走了1个位置但下标1的值是3直接一步干到终点。这就叫“一失足成千古恨”。所以这道题里“每步跳最远”不是真正的贪心是贪小便宜吃大亏。2.2 正确的贪心视角把每一步看成一次区间覆盖真正的贪心策略需要换个角度看问题。不要把“跳一次”理解成“走到某个点”要理解成“这次跳跃覆盖了从当前位置到最远位置之间的一段区间”。在这个区间里的任意一个点你都可以作为下一次跳跃的起点。那么问题就变成了已知当前这一跳能覆盖到[当前位置, 当前边界]这一段我该选区间里的哪个点作为下一次的起跳点才能让下一次的覆盖范围最远答案是不用急着选。你可以一边往右走一边记录这段区间内所有点能跳到的最远位置。当你走到这段区间的右边界时说明这一跳能覆盖的范围你已经全部看完了此时你已经知道了“在这些点里起跳能跳到的最远位置是多少”。这时候再跳一次把这个最远位置作为新的覆盖边界。用大白话说我不在起点决定跳到哪个点我先把这一跳能踩到的所有点都扫一遍看看哪个点潜力最大然后在这一跳的边界处统一做决策。这样既不会错过区间内的任何一个潜力股又保证了每一步都朝着“覆盖最远”的方向推进。2.3 为什么局部最优能推出全局最优这是整道题的灵魂问题面试官最常追问的点就在这里。贪心算法的成立条件说白了就两条贪心选择性质和无后效性。跳跃游戏2恰好都满足。先看无后效性。你站在哪个位置决定了你下一步能跳多远但注意这里的“能力”只取决于当前位置的值跟你之前是怎么跳到这个位置的完全无关。不管你是跳了3次到的这里还是跳了5次到的这里只要到了这个点后面的可能性就一模一样。这就意味着在边界相同时跳跃次数更少的那条路肯定更好不需要回溯比较。再看贪心选择性质。每次在当前可覆盖范围内选择能延伸最远的下一个点为什么不会错因为“下一步能延伸到的最远位置”是唯一值得关注的指标。如果存在一个最优解它第一步落在了某个点k而你在所有可选项里选的点p能延伸到更远的位置那么你可以把最优解的第一步替换成p后续的跳跃计划原封不动地执行因为p的覆盖范围包含了k的覆盖范围k能到达的所有点p也都能到达。这样替换后步数不会增加甚至可能减少。这就证明了贪心选择的正确性。我把这层逻辑用程序员的话再翻译一遍你只需要维护两个变量——当前这一跳的边界end和遍历过程中发现的最远可达位置maxPos扫到end的时候强制跳一步把end更新成maxPos然后继续扫。整个算法就是一个线性扫描没有任何回头路。这个思想在生活里也很好理解。比如你在一个陌生商场里要坐直梯到顶楼你当前只在2楼能走到3楼或4楼4楼有另一部直梯能到8楼3楼有另一部直梯能到6楼。贪心策略不是让你一上来就冲到4楼而是让你先看看2楼这一层能到达的3楼和4楼里谁对应的下一段路线上限最高。因为你反正都要经过这些楼层不如把选择权留到最后统一评估。3. 核心实现单次遍历O(n)解法3.1 两个核心变量end与maxPos搞懂贪心思想之后实现其实就几行代码。但代码越短越容易掉进细节陷阱里所以我还是打算把每个变量掰开揉碎讲一遍。先看完整代码我用C写逻辑清晰方便对照讲解。class Solution { public: int jump(vectorint nums) { int n nums.size(); if (n 1) { return 0; // 已经在最后一个位置不需要跳 } int step 0; // 已经跳的次数 int end 0; // 当前这一跳能覆盖到的右边界 int maxPos 0; // 扫描过程中能到达的最远位置 for (int i 0; i n - 1; i) { maxPos max(maxPos, i nums[i]); if (i end) { step; end maxPos; } } return step; } };这里三个变量各司其职end是“当前这一跳已经确定的覆盖边界”。在没达到这个位置之前我还没有做完这一跳的决策一旦扫到了这个位置说明这一跳的潜力已经全部看完了必须跳出去跳到maxPos这个位置或更远。maxPos是一个流动更新的最大值它在整个扫描过程中持续记录“如果我现在跳一步能到达的最远位置”。注意它不只是在当前位置求最大值而是在已经扫过的所有位置里取i nums[i]的最大值。step不用多解释就是当前累计的跳跃次数。为什么循环条件是i n - 1而不是i n因为最后一个位置根本不需要再跳了题目问的是跳到最后一个位置的最小次数不是跳出数组。而且如果循环到i n - 1时恰好满足i end还会多做一次无用的step结果会偏大。这是这道题最经典的边界坑下面我会再细说。3.2 用样例走一遍完整过程空讲代码不够直观我们拿nums [2, 3, 1, 1, 4]手动走一遍。初始状态i0, end0, maxPos0, step0。第一步i0。maxPos max(0, 0 2) 2。这时候检查i end确实相等都是0说明我们已经走到了这一跳能覆盖范围的边界必须做一次跳跃决策。于是step 1end maxPos 2。第二步i1。maxPos max(2, 1 3) 4。此时i1end2两者不相等说明我们还在第一跳的覆盖范围内还没走到边界不需要做决策继续扫描。第三步i2。maxPos max(4, 2 1) 4。此时i2end2相等了。说明第一跳覆盖范围的右边界已经到了而且在这期间我们已经发现从下标1起跳可以到达最远下标4。于是做第二次跳跃决策step 2end maxPos 4。第四步i3。maxPos max(4, 3 1) 4。此时i3end4不相等。循环到i n - 1就结束了因为n5n-14i最多到3。最终返回step 2和预期一致。这个过程中最值得玩味的是第二步。当i1时我们其实已经发现maxPos变成了4但并没有立刻把end改成4也没有立刻增加step。为什么因为i1还处于第一次跳跃的覆盖范围内我们还在“第一次跳跃”的旅程中还没到边界。直到i2到达了第一跳的边界end2我们才正式结束第一跳同时开启第二跳并把end更新为这段时间内观察到的最远可达点4。我再用区间覆盖的思路翻译一遍第一跳覆盖了[0, 2]这三个位置。在扫描这三个位置的过程中我们发现下标1的潜力最大能延伸到4。所以当第一跳走到边界2时我们落地到下标1相当于从0跳到1然后紧接着从1出发把第二跳的覆盖范围更新为[1, 4]。后面几跳以此类推。3.3 为什么这段代码能“边扫边跳”而不出错有人可能会问代码里根本没有显式记录“我落在了哪个位置”为什么i从0走到1、走到2就能代表“我实际到达了这些位置”这是因为在这道题里“我处于哪个位置”并不影响我下一步的决策影响决策的只有“当前覆盖边界end和已知的全局最远可达点maxPos”。你可以把i理解为“扫描指针”它从0开始一路向右推进它扫描过的所有位置都是“当前这一跳覆盖范围内能到达的位置”。因为题目保证每一步都能落在覆盖范围内所以扫到i就意味着“我有可能站在i这个位置起跳”而maxPos已经替你算好了从这些位置出发最远能到哪。这就是这段代码最精妙的地方它不需要模拟真实跳跃的落脚点只需要一个扫描指针、一个边界值、一个可达最远值就能在O(n)时间内求出答案连额外的数组都不用开。4. 边界条件与调试技巧最容易栽的三个地方4.1 数组长度为1时直接返回0这是测试用例里最常见的坑之一。如果nums [0]你已经在终点答案当然是0。如果nums [5]你也在终点答案还是0。数组只有一个元素时无论里面的值多大都不需要跳。用if (n 1) return 0;单独处理或者让循环条件变成i n - 1两者都能保证这一点。我建议两件事都做因为单独判断能让代码意图更明显面试时也容易给自己留出讨论空间。顺便说一句nums [2, 1]这种两个元素的数组也要注意。n2循环里只有i0一次迭代。maxPos max(0, 02) 2i endstep1end2循环结束返回1。逻辑正确。如果循环条件写错了写到i n那么i1时还会再执行一次maxPos max(2, 11) 2此时i end也成立step会再加1变成2答案错误。4.2 当前位置值为0会不会死循环或跳不出去题目保证一定能到达终点所以严格来说你不会遇到“0卡住跳不出去”的情况。但在实际做题时如果你想用这个解法去处理那些不保证可达的变种题比如LeetCode 55跳跃游戏就应该警惕这个情况。在LeetCode 55中你只需要判断能否到达终点解法更简单用一个变量maxPos记录当前能到达的最远位置遍历过程中如果i maxPos说明当前位置已经不可达直接返回false。因为题目只求“能不能”不需要求“最少几步”所以跳跃计数逻辑可以去掉。回到45题虽然题目保证可达但如果你在本地测试时用了自定义用例比如nums [1, 0, 1]代码会怎样i0时maxPos 1end变成1step1i1时maxPos max(1, 10) 1此时i endstep2end1。到这里end没有前进如果继续遍历会发现i会一直等于endstep会一直增加。但在45题的约束下不会出现这种情况因为题目标准输入保证nums[0]一定可以通向终点。不过了解这个边界可以帮你理解为什么LeetCode官方说“题目数据保证可以到达nums[n-1]”。4.3 跳跃长度超过数组长度时的处理nums [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]这种极端情况也很好理解。i0时maxPos 10一步就能到达最后一个位置step1。i会一直扫描到n-2但因为end10而i最大只能到9所以i end的触发条件不会再成立step不会继续增加。循环结束后返回1完全正确。这类“超长跳跃”在面试时可以用来快速验证你的end更新逻辑是否正确。我见过不少人在maxPos max(maxPos, i nums[i])这一步上掉以轻心把i nums[i]算成nums[i]或者漏加了i导致所有超过当前位置的值都被少算了一段距离。记住nums[i]是相对偏移量必须加上当前位置下标才是绝对位置。4.4 调试技巧打印关键变量一眼定位问题如果你在练习时发现自己写的版本结果不对我推荐一个非常高效的调试方式在循环体里打印i、nums[i]、maxPos、end、step五个值手动走一遍样例很快就能定位到是边界更新时机的问题还是初始值的问题。for (int i 0; i n - 1; i) { maxPos max(maxPos, i nums[i]); printf(i%d num%d maxPos%d end%d step%d\n, i, nums[i], maxPos, end, step); if (i end) { step; end maxPos; } }输出结果会直观地告诉你end是什么时候被推着往前走的maxPos有没有在关键时刻更新到位。我调试这道题时就靠这行日志发现了一个很隐蔽的错误——我一开始把maxPos初始化为nums[0]然后从i1开始遍历导致i0时end更新不及时输出结果偏大。5. 贪心思想延伸从跳跃游戏到背包问题5.1 分数背包问题为什么能直接贪心聊完跳跃游戏2顺便聊聊“背包问题贪心算法”这一个热词因为很多人学贪心的时候会在跳跃游戏和背包问题之间来回穿梭搞不清哪些题能贪哪些题不能贪。背包问题有两个经典版本分数背包Fractional Knapsack和0/1背包。分数背包的特点是物品可以拆分比如带了10千克黄金你可以只装5千克。这种情况下贪心策略非常简单粗暴按照单位重量价值价值/重量从高到低排序能装多少装多少装到背包容量用完为止。为什么分数背包贪心是安全的因为物品可以拆分你不需要做“选A还是选B”的排他性决策。每一步都在“当前单位价值最高的那部分物品”上做选择而单位价值是独立可比的先拿价值高的那部分永远不会影响后续选择。这跟在跳跃游戏里“先在当前区间找一个最远的点”本质上是同构的——你在一个连续的决策空间里做增量选择局部最优不会改变未来的可能性空间。5.2 0/1背包为什么不能直接贪心0/1背包就完全是另一码事了。每个物品只能整件拿或不拿不可拆分。这时候如果你按照单位价值排序贪心很可能会翻车。我举个例子背包容量10三个物品——物品A重量6价值12单位价值2物品B重量5价值10单位价值2物品C重量5价值8单位价值1.6。贪心按单位价值排序先拿A或者B单位价值一样假设先拿A占用容量6剩下容量4什么都装不了总价值12。但最优方案是拿B和C总重量10总价值18直接碾压贪心结果。问题出在哪出在0/1背包有“容量碎片”问题。你拿了一个大件物品后剩余容量可能不够再装另一个有价值的物品而贪心算法完全没有考虑这种组合效应。这就是典型的“局部最优不等于全局最优”案例。5.3 区分“能贪心”和“不能贪心”的通用判据把跳跃游戏2、分数背包、0/1背包放在一起对比可以提炼出一个通用的判断标准贪心成立的题决策空间必须是连续可比较的或者局部决策不会改变后续决策的收益结构。在跳跃游戏2里我选择站在哪个位置起跳不会改变“覆盖范围越远越好”这个评价标准也不会改变数组里每个数字的值所以可以贪心。在分数背包里装下单位价值最高的部分不会影响剩余物品的相对价值排序所以可以贪心。而在0/1背包里装下某个物品会占用容量改变剩余容量能容纳的其他物品组合进而改变后续决策的收益结构所以不能贪心只能动态规划。这个判据在实际刷题时非常有用。遇到一个新题先问自己两个问题第一局部最优能直接导向全局最优吗第二做了一次选择之后剩余问题的结构有没有发生变化如果答案都是“是”基本可以放心用贪心只要有一个“否”就老老实实回到DP。5.4 跳跃游戏2背后“区间覆盖”能力的迁移其实跳跃游戏2的核心思想还能迁移到很多其他问题上比如“区间合并”LeetCode 56、“会议室II”LeetCode 253和“最小区间覆盖”LeetCode 1024。这些题都有一个共同特征给你一组区间让你用最少的区间覆盖目标范围或者判断区间能否完全覆盖某个连续段。最小区间覆盖那道题几乎就是跳跃游戏2的换皮版本。给定一个目标区间[0, n)和一堆互不重叠的子区间让你用最少的子区间完整覆盖目标区间。解法是排序后贪心选择能延伸最远的区间逻辑跟跳跃游戏一模一样当前已覆盖范围是end在所有左侧不超过end的区间里挑右侧最远的一个更新end计数加一。你把子区间换成“从每个位置能跳到的范围”题干换个人物角色算法不变。这就是为什么我建议大家不要只背跳跃游戏2的代码而是把“覆盖最远”这个思维模型吃透。面试时如果遇到变种题你能一眼看出它本质是同一类问题答题的底气和速度都不一样。6. 常见问题与实战经验那些年我们踩过的坑6.1 为什么我的代码会TLE或者内存超限TLE最常见的原因是有人一开始用了DFS回溯枚举所有跳跃路径再把所有路径长度取最小。数据量大一点直接超时因为这本质上是指数级搜索。我还见过一种“伪动规”写法开一个dp[n]数组dp[i]表示从0跳到i的最小步数然后两层循环更新复杂度O(n^2)。LeetCode上45题的数据范围是1 nums.length 10^4O(n^2)在某些语言里勉强能过但面试官一定会追问“能不能优化成O(n)”。如果你只准备了DP解法现场改贪心会很被动。所以我的建议是45题直接上贪心解法DP了解思路即可。DP递推公式是dp[j] min(dp[j], dp[i] 1)其中i j且i nums[i] j。这个公式理解起来不难但真要写还得考虑初始化、边界、内层循环范围代码量比贪心多一倍不止。6.2 如何快速验证贪心策略是否正确贪心算法最大的风险不是代码写错而是策略本身是错的。跑过了样例不代表正确一定要自己构造反例测试。我常用的验证方法有三板斧。第一板斧拿官方样例跑通然后自己构造三个极端数据全都是1的数组、第一个元素特别大的数组、中间某个值为0的数组看输出是否符合直觉。第二板斧写一个暴力DFS解法作为benchmark在小规模数据上随机生成数组对比贪心解法和暴力解法的输出如果有一组不一致说明贪心策略有问题。第三板斧想清楚被“贪”掉的方案为什么不可能比当前方案更优这一步是数学证明代码层面验证不了。我在刷这道题的时候第一板斧和第二板斧都用了。随机生成500组长度不超过8的数组暴力枚举所有路径对比贪心输出全部一致我才彻底放心。这个习惯建议保留尤其是面试前几天刷题时用暴力验证法能帮你快速排除很多“你以为对其实不对”的题解。6.3 面试中回答这道题的节奏建议如果你在面试中遇到这道题我建议按照下面这个节奏来回答既显得思路清晰又不会暴露出“只会背题”的短板。第一步先复述题意并明确一个关键点“每个位置能跳到的是一个区间而不是一个点”。第二步抛出反例主动说“如果每一步都选跳得最远的位置会遇到什么问题”然后拿出[2, 3, 1, 1, 4]这个例子说明为什么贪婪距离会失败。第三步提出区间覆盖视角说明我选择在“这一跳的边界”处做决策维护当前覆盖边界end和全局可达最远位置maxPos遍历一遍就能得出答案。第四步给出代码并分析复杂度时间O(n)空间O(1)。第五步如果你想让面试官眼前一亮可以补充一句“这道题的end触发性更新本质上是把一次跳跃看成一个阶段每个阶段结束时把边界延伸到maxPos所以算法也叫BFS的压缩版本。”最后一条是杀手锏。你想想跳跃游戏每跳一次是一层覆盖范围内的所有点都是该层的节点而maxPos记录的是下一层能到达的右边界。这不是BFS是什么只不过BFS需要队列这里压缩成两个变量就够了。6.4 我自己刷题时的三个心得心得一别急着写代码。我第一遍做这道题时上来就想“最小步数DP”写了三四十行代码提交后还沾沾自喜。结果后来看官方题解发现一个O(n)的贪心就能解决当场有点脸热。从那以后凡是看到“最值”类题目我都会先花两分钟想想“有没有贪心性质”再决定要不要上DP。这个习惯帮我省了很多时间。心得二边界要一上来就想清楚。n 1返回0、循环到n-2而不是n-1、maxPos初始化为0而不是nums[0]这三个点只要错一个答案就是错的。我建议把这三条写成注释放在代码旁边防止以后回来看的时候又踩一遍。心得三拓展题一定要做。做完了跳跃游戏2我建议立刻去做LeetCode 55跳跃游戏、LeetCode 1024视频拼接和LeetCode 45的变种“如果要求输出路径”。输出路径的解法是在贪心更新step的时候记录下当时选择的下标然后根据记录的路径反向追踪。代码也不复杂vectorint jumpPath(vectorint nums) { int n nums.size(); int step 0, end 0, maxPos 0, chosen 0; vectorint path; for (int i 0; i n - 1; i) { if (i nums[i] maxPos) { maxPos i nums[i]; chosen i; } if (i end) { path.push_back(chosen); end maxPos; step; } } return path; }这样路径就记录在path里了。面试时如果能把这个变种也答出来基本等于告诉面试官“这道题我不仅是会背是理解了”。7. 写在最后贪心这条路上的“先证明后放心”回头再看跳跃游戏2这道题它最值得学习的不是那几行代码而是“为什么贪心可以用”的整套思考过程。我第一次做这道题时即使看了题解心里也一直犯嘀咕凭什么扫一遍就敢说这是最优解后来把反例、证明、暴力验证全走了一遍才彻底放下心来。这也是我觉得贪心算法最迷人的地方——它看起来特别“投机取巧”但背后有严谨的数学逻辑兜底。你写的那几行代码看似只是简单地取最大值、更新边界实际上每一步都在证明“不存在比这更优的路径”。这种“一眼看穿问题本质”的能力才是刷题最该练的东西。如果你现在正在准备面试或者正在刷leecode100的题单我建议你把这道题和背包问题放在同一天看。跳跃游戏2代表“连续决策空间的贪心”分数背包代表“增量选择空间的贪心”0/1背包代表“离散组合空间不能贪心”。三个题摆在一起你对贪心算法的理解会有一个质的提升。最后分享一个小技巧刷题时不要只追求AC试着在代码旁边写一行注释说明这个变量为什么这么更新那个边界为什么这样处理。写不出来的地方就是你还没真正理解的地方。我自己的代码里end maxPos这行旁边的注释写的是“这一跳最大的收益已确定开始下一跳”。写完这句话之后这道题我再也没错过。 贪心算法经典题：LeetCode 45跳跃游戏II最小步数解法解析
1. 题目到底在问什么最小步数是“跳”出来的不是“算”出来的看到“跳跃游戏2”这个标题刷过题的朋友基本都会心一笑这是LeetCode 45题也是leecode100高频题单里绕不开的一道经典。第一次接触“最小跳跃次数”这六个字大多数人第一反应是动态规划——毕竟“最小XX”四个字天然带着DP的味道状态转移方程推一推样例跑一跑好像也能过。但如果你真的拿DP去解这道题等你把O(n^2)的代码写完再看到评论区那个一行扫描的贪心解法会觉得自己像个傻子。这道题的意思本身不复杂给你一个非负整数数组nums你一开始站在下标0的位置。数组里每个数字代表你在该位置最多能往前跳多少步比如nums[2] 3意思是你站在下标2时最多可以跳到下标5也可以只跳1步到下标3或者跳2步到下标4。目标是从下标0跳到最后一位问你最少需要跳几次。注意这里不是说只能跳到恰好等于位置值的地方“最多”两个字很关键。也就是说当前位置可以覆盖一段连续的区间你可以在这个区间里任意选择落脚点。题目保证了一定能跳到最后一位我后面会专门说这个“保证”有多重要所以你不需要处理“到不了”的情况只需要求最小次数。举个例子nums [2, 3, 1, 1, 4]。从0出发可以跳1步到下标1也可以跳2步到下标2。如果先跳到下标2这一步跳最远然后从下标2最多只能跳1步到下标3再从下标3跳1步到终点下标4一共3次。但最优解是先从0跳到下标1因为下标1的值是3直接一步跳到终点总共只需要2次。这个例子特别有杀伤力它直接干掉了一种很自然的错误思路——“每次都跳最远”。你想如果每一步都贪心地跳最远第一步跳到下标2结果反而绕远了。这就是为什么“跳跃游戏2”值得单独讲它教会你的不只是一道题而是贪心算法里一个极其重要的思想贪的不是眼前这一步的远近而是下一步的可达范围。这道题适合谁来学如果你在准备大厂算法面试、刷leecode100作为题库或者刚开始接触贪心算法想找几个经典案例练手这道题都值得你花半小时彻底搞懂。它的代码短到只有几行但里面的边界处理和贪心证明逻辑能把一个“感觉自己会贪心”的人打回原形。2. 贪心算法的选型思考从“跳得远”到“覆盖得远”2.1 常见的错误贪心每一步都跳最远先说说那道错误答案为什么错因为很多人第一眼就会踩进去。如果把问题简化成“当前能跳多远就跳多远”直觉上会觉得每次消耗最少的步数就能覆盖最大的距离那总步数不是最少吗这个直觉只对了一部分。问题在于你当前这一步跳得远并不代表你下一步还能跳得远。跳跃能力是跟着你的“脚下位置”走的而不是跟着你“已经走过的距离”走的。[2, 3, 1, 1, 4]这个例子就是最好的反例。从0开始能跳2步最远到下标2。你以为你赚了结果下标2的值只有1你下一步最远只能到3然后还得再跳一次到4。而如果你没跳那么远而是跳到下标1虽然这一步只走了1个位置但下标1的值是3直接一步干到终点。这就叫“一失足成千古恨”。所以这道题里“每步跳最远”不是真正的贪心是贪小便宜吃大亏。2.2 正确的贪心视角把每一步看成一次区间覆盖真正的贪心策略需要换个角度看问题。不要把“跳一次”理解成“走到某个点”要理解成“这次跳跃覆盖了从当前位置到最远位置之间的一段区间”。在这个区间里的任意一个点你都可以作为下一次跳跃的起点。那么问题就变成了已知当前这一跳能覆盖到[当前位置, 当前边界]这一段我该选区间里的哪个点作为下一次的起跳点才能让下一次的覆盖范围最远答案是不用急着选。你可以一边往右走一边记录这段区间内所有点能跳到的最远位置。当你走到这段区间的右边界时说明这一跳能覆盖的范围你已经全部看完了此时你已经知道了“在这些点里起跳能跳到的最远位置是多少”。这时候再跳一次把这个最远位置作为新的覆盖边界。用大白话说我不在起点决定跳到哪个点我先把这一跳能踩到的所有点都扫一遍看看哪个点潜力最大然后在这一跳的边界处统一做决策。这样既不会错过区间内的任何一个潜力股又保证了每一步都朝着“覆盖最远”的方向推进。2.3 为什么局部最优能推出全局最优这是整道题的灵魂问题面试官最常追问的点就在这里。贪心算法的成立条件说白了就两条贪心选择性质和无后效性。跳跃游戏2恰好都满足。先看无后效性。你站在哪个位置决定了你下一步能跳多远但注意这里的“能力”只取决于当前位置的值跟你之前是怎么跳到这个位置的完全无关。不管你是跳了3次到的这里还是跳了5次到的这里只要到了这个点后面的可能性就一模一样。这就意味着在边界相同时跳跃次数更少的那条路肯定更好不需要回溯比较。再看贪心选择性质。每次在当前可覆盖范围内选择能延伸最远的下一个点为什么不会错因为“下一步能延伸到的最远位置”是唯一值得关注的指标。如果存在一个最优解它第一步落在了某个点k而你在所有可选项里选的点p能延伸到更远的位置那么你可以把最优解的第一步替换成p后续的跳跃计划原封不动地执行因为p的覆盖范围包含了k的覆盖范围k能到达的所有点p也都能到达。这样替换后步数不会增加甚至可能减少。这就证明了贪心选择的正确性。我把这层逻辑用程序员的话再翻译一遍你只需要维护两个变量——当前这一跳的边界end和遍历过程中发现的最远可达位置maxPos扫到end的时候强制跳一步把end更新成maxPos然后继续扫。整个算法就是一个线性扫描没有任何回头路。这个思想在生活里也很好理解。比如你在一个陌生商场里要坐直梯到顶楼你当前只在2楼能走到3楼或4楼4楼有另一部直梯能到8楼3楼有另一部直梯能到6楼。贪心策略不是让你一上来就冲到4楼而是让你先看看2楼这一层能到达的3楼和4楼里谁对应的下一段路线上限最高。因为你反正都要经过这些楼层不如把选择权留到最后统一评估。3. 核心实现单次遍历O(n)解法3.1 两个核心变量end与maxPos搞懂贪心思想之后实现其实就几行代码。但代码越短越容易掉进细节陷阱里所以我还是打算把每个变量掰开揉碎讲一遍。先看完整代码我用C写逻辑清晰方便对照讲解。class Solution { public: int jump(vectorint nums) { int n nums.size(); if (n 1) { return 0; // 已经在最后一个位置不需要跳 } int step 0; // 已经跳的次数 int end 0; // 当前这一跳能覆盖到的右边界 int maxPos 0; // 扫描过程中能到达的最远位置 for (int i 0; i n - 1; i) { maxPos max(maxPos, i nums[i]); if (i end) { step; end maxPos; } } return step; } };这里三个变量各司其职end是“当前这一跳已经确定的覆盖边界”。在没达到这个位置之前我还没有做完这一跳的决策一旦扫到了这个位置说明这一跳的潜力已经全部看完了必须跳出去跳到maxPos这个位置或更远。maxPos是一个流动更新的最大值它在整个扫描过程中持续记录“如果我现在跳一步能到达的最远位置”。注意它不只是在当前位置求最大值而是在已经扫过的所有位置里取i nums[i]的最大值。step不用多解释就是当前累计的跳跃次数。为什么循环条件是i n - 1而不是i n因为最后一个位置根本不需要再跳了题目问的是跳到最后一个位置的最小次数不是跳出数组。而且如果循环到i n - 1时恰好满足i end还会多做一次无用的step结果会偏大。这是这道题最经典的边界坑下面我会再细说。3.2 用样例走一遍完整过程空讲代码不够直观我们拿nums [2, 3, 1, 1, 4]手动走一遍。初始状态i0, end0, maxPos0, step0。第一步i0。maxPos max(0, 0 2) 2。这时候检查i end确实相等都是0说明我们已经走到了这一跳能覆盖范围的边界必须做一次跳跃决策。于是step 1end maxPos 2。第二步i1。maxPos max(2, 1 3) 4。此时i1end2两者不相等说明我们还在第一跳的覆盖范围内还没走到边界不需要做决策继续扫描。第三步i2。maxPos max(4, 2 1) 4。此时i2end2相等了。说明第一跳覆盖范围的右边界已经到了而且在这期间我们已经发现从下标1起跳可以到达最远下标4。于是做第二次跳跃决策step 2end maxPos 4。第四步i3。maxPos max(4, 3 1) 4。此时i3end4不相等。循环到i n - 1就结束了因为n5n-14i最多到3。最终返回step 2和预期一致。这个过程中最值得玩味的是第二步。当i1时我们其实已经发现maxPos变成了4但并没有立刻把end改成4也没有立刻增加step。为什么因为i1还处于第一次跳跃的覆盖范围内我们还在“第一次跳跃”的旅程中还没到边界。直到i2到达了第一跳的边界end2我们才正式结束第一跳同时开启第二跳并把end更新为这段时间内观察到的最远可达点4。我再用区间覆盖的思路翻译一遍第一跳覆盖了[0, 2]这三个位置。在扫描这三个位置的过程中我们发现下标1的潜力最大能延伸到4。所以当第一跳走到边界2时我们落地到下标1相当于从0跳到1然后紧接着从1出发把第二跳的覆盖范围更新为[1, 4]。后面几跳以此类推。3.3 为什么这段代码能“边扫边跳”而不出错有人可能会问代码里根本没有显式记录“我落在了哪个位置”为什么i从0走到1、走到2就能代表“我实际到达了这些位置”这是因为在这道题里“我处于哪个位置”并不影响我下一步的决策影响决策的只有“当前覆盖边界end和已知的全局最远可达点maxPos”。你可以把i理解为“扫描指针”它从0开始一路向右推进它扫描过的所有位置都是“当前这一跳覆盖范围内能到达的位置”。因为题目保证每一步都能落在覆盖范围内所以扫到i就意味着“我有可能站在i这个位置起跳”而maxPos已经替你算好了从这些位置出发最远能到哪。这就是这段代码最精妙的地方它不需要模拟真实跳跃的落脚点只需要一个扫描指针、一个边界值、一个可达最远值就能在O(n)时间内求出答案连额外的数组都不用开。4. 边界条件与调试技巧最容易栽的三个地方4.1 数组长度为1时直接返回0这是测试用例里最常见的坑之一。如果nums [0]你已经在终点答案当然是0。如果nums [5]你也在终点答案还是0。数组只有一个元素时无论里面的值多大都不需要跳。用if (n 1) return 0;单独处理或者让循环条件变成i n - 1两者都能保证这一点。我建议两件事都做因为单独判断能让代码意图更明显面试时也容易给自己留出讨论空间。顺便说一句nums [2, 1]这种两个元素的数组也要注意。n2循环里只有i0一次迭代。maxPos max(0, 02) 2i endstep1end2循环结束返回1。逻辑正确。如果循环条件写错了写到i n那么i1时还会再执行一次maxPos max(2, 11) 2此时i end也成立step会再加1变成2答案错误。4.2 当前位置值为0会不会死循环或跳不出去题目保证一定能到达终点所以严格来说你不会遇到“0卡住跳不出去”的情况。但在实际做题时如果你想用这个解法去处理那些不保证可达的变种题比如LeetCode 55跳跃游戏就应该警惕这个情况。在LeetCode 55中你只需要判断能否到达终点解法更简单用一个变量maxPos记录当前能到达的最远位置遍历过程中如果i maxPos说明当前位置已经不可达直接返回false。因为题目只求“能不能”不需要求“最少几步”所以跳跃计数逻辑可以去掉。回到45题虽然题目保证可达但如果你在本地测试时用了自定义用例比如nums [1, 0, 1]代码会怎样i0时maxPos 1end变成1step1i1时maxPos max(1, 10) 1此时i endstep2end1。到这里end没有前进如果继续遍历会发现i会一直等于endstep会一直增加。但在45题的约束下不会出现这种情况因为题目标准输入保证nums[0]一定可以通向终点。不过了解这个边界可以帮你理解为什么LeetCode官方说“题目数据保证可以到达nums[n-1]”。4.3 跳跃长度超过数组长度时的处理nums [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]这种极端情况也很好理解。i0时maxPos 10一步就能到达最后一个位置step1。i会一直扫描到n-2但因为end10而i最大只能到9所以i end的触发条件不会再成立step不会继续增加。循环结束后返回1完全正确。这类“超长跳跃”在面试时可以用来快速验证你的end更新逻辑是否正确。我见过不少人在maxPos max(maxPos, i nums[i])这一步上掉以轻心把i nums[i]算成nums[i]或者漏加了i导致所有超过当前位置的值都被少算了一段距离。记住nums[i]是相对偏移量必须加上当前位置下标才是绝对位置。4.4 调试技巧打印关键变量一眼定位问题如果你在练习时发现自己写的版本结果不对我推荐一个非常高效的调试方式在循环体里打印i、nums[i]、maxPos、end、step五个值手动走一遍样例很快就能定位到是边界更新时机的问题还是初始值的问题。for (int i 0; i n - 1; i) { maxPos max(maxPos, i nums[i]); printf(i%d num%d maxPos%d end%d step%d\n, i, nums[i], maxPos, end, step); if (i end) { step; end maxPos; } }输出结果会直观地告诉你end是什么时候被推着往前走的maxPos有没有在关键时刻更新到位。我调试这道题时就靠这行日志发现了一个很隐蔽的错误——我一开始把maxPos初始化为nums[0]然后从i1开始遍历导致i0时end更新不及时输出结果偏大。5. 贪心思想延伸从跳跃游戏到背包问题5.1 分数背包问题为什么能直接贪心聊完跳跃游戏2顺便聊聊“背包问题贪心算法”这一个热词因为很多人学贪心的时候会在跳跃游戏和背包问题之间来回穿梭搞不清哪些题能贪哪些题不能贪。背包问题有两个经典版本分数背包Fractional Knapsack和0/1背包。分数背包的特点是物品可以拆分比如带了10千克黄金你可以只装5千克。这种情况下贪心策略非常简单粗暴按照单位重量价值价值/重量从高到低排序能装多少装多少装到背包容量用完为止。为什么分数背包贪心是安全的因为物品可以拆分你不需要做“选A还是选B”的排他性决策。每一步都在“当前单位价值最高的那部分物品”上做选择而单位价值是独立可比的先拿价值高的那部分永远不会影响后续选择。这跟在跳跃游戏里“先在当前区间找一个最远的点”本质上是同构的——你在一个连续的决策空间里做增量选择局部最优不会改变未来的可能性空间。5.2 0/1背包为什么不能直接贪心0/1背包就完全是另一码事了。每个物品只能整件拿或不拿不可拆分。这时候如果你按照单位价值排序贪心很可能会翻车。我举个例子背包容量10三个物品——物品A重量6价值12单位价值2物品B重量5价值10单位价值2物品C重量5价值8单位价值1.6。贪心按单位价值排序先拿A或者B单位价值一样假设先拿A占用容量6剩下容量4什么都装不了总价值12。但最优方案是拿B和C总重量10总价值18直接碾压贪心结果。问题出在哪出在0/1背包有“容量碎片”问题。你拿了一个大件物品后剩余容量可能不够再装另一个有价值的物品而贪心算法完全没有考虑这种组合效应。这就是典型的“局部最优不等于全局最优”案例。5.3 区分“能贪心”和“不能贪心”的通用判据把跳跃游戏2、分数背包、0/1背包放在一起对比可以提炼出一个通用的判断标准贪心成立的题决策空间必须是连续可比较的或者局部决策不会改变后续决策的收益结构。在跳跃游戏2里我选择站在哪个位置起跳不会改变“覆盖范围越远越好”这个评价标准也不会改变数组里每个数字的值所以可以贪心。在分数背包里装下单位价值最高的部分不会影响剩余物品的相对价值排序所以可以贪心。而在0/1背包里装下某个物品会占用容量改变剩余容量能容纳的其他物品组合进而改变后续决策的收益结构所以不能贪心只能动态规划。这个判据在实际刷题时非常有用。遇到一个新题先问自己两个问题第一局部最优能直接导向全局最优吗第二做了一次选择之后剩余问题的结构有没有发生变化如果答案都是“是”基本可以放心用贪心只要有一个“否”就老老实实回到DP。5.4 跳跃游戏2背后“区间覆盖”能力的迁移其实跳跃游戏2的核心思想还能迁移到很多其他问题上比如“区间合并”LeetCode 56、“会议室II”LeetCode 253和“最小区间覆盖”LeetCode 1024。这些题都有一个共同特征给你一组区间让你用最少的区间覆盖目标范围或者判断区间能否完全覆盖某个连续段。最小区间覆盖那道题几乎就是跳跃游戏2的换皮版本。给定一个目标区间[0, n)和一堆互不重叠的子区间让你用最少的子区间完整覆盖目标区间。解法是排序后贪心选择能延伸最远的区间逻辑跟跳跃游戏一模一样当前已覆盖范围是end在所有左侧不超过end的区间里挑右侧最远的一个更新end计数加一。你把子区间换成“从每个位置能跳到的范围”题干换个人物角色算法不变。这就是为什么我建议大家不要只背跳跃游戏2的代码而是把“覆盖最远”这个思维模型吃透。面试时如果遇到变种题你能一眼看出它本质是同一类问题答题的底气和速度都不一样。6. 常见问题与实战经验那些年我们踩过的坑6.1 为什么我的代码会TLE或者内存超限TLE最常见的原因是有人一开始用了DFS回溯枚举所有跳跃路径再把所有路径长度取最小。数据量大一点直接超时因为这本质上是指数级搜索。我还见过一种“伪动规”写法开一个dp[n]数组dp[i]表示从0跳到i的最小步数然后两层循环更新复杂度O(n^2)。LeetCode上45题的数据范围是1 nums.length 10^4O(n^2)在某些语言里勉强能过但面试官一定会追问“能不能优化成O(n)”。如果你只准备了DP解法现场改贪心会很被动。所以我的建议是45题直接上贪心解法DP了解思路即可。DP递推公式是dp[j] min(dp[j], dp[i] 1)其中i j且i nums[i] j。这个公式理解起来不难但真要写还得考虑初始化、边界、内层循环范围代码量比贪心多一倍不止。6.2 如何快速验证贪心策略是否正确贪心算法最大的风险不是代码写错而是策略本身是错的。跑过了样例不代表正确一定要自己构造反例测试。我常用的验证方法有三板斧。第一板斧拿官方样例跑通然后自己构造三个极端数据全都是1的数组、第一个元素特别大的数组、中间某个值为0的数组看输出是否符合直觉。第二板斧写一个暴力DFS解法作为benchmark在小规模数据上随机生成数组对比贪心解法和暴力解法的输出如果有一组不一致说明贪心策略有问题。第三板斧想清楚被“贪”掉的方案为什么不可能比当前方案更优这一步是数学证明代码层面验证不了。我在刷这道题的时候第一板斧和第二板斧都用了。随机生成500组长度不超过8的数组暴力枚举所有路径对比贪心输出全部一致我才彻底放心。这个习惯建议保留尤其是面试前几天刷题时用暴力验证法能帮你快速排除很多“你以为对其实不对”的题解。6.3 面试中回答这道题的节奏建议如果你在面试中遇到这道题我建议按照下面这个节奏来回答既显得思路清晰又不会暴露出“只会背题”的短板。第一步先复述题意并明确一个关键点“每个位置能跳到的是一个区间而不是一个点”。第二步抛出反例主动说“如果每一步都选跳得最远的位置会遇到什么问题”然后拿出[2, 3, 1, 1, 4]这个例子说明为什么贪婪距离会失败。第三步提出区间覆盖视角说明我选择在“这一跳的边界”处做决策维护当前覆盖边界end和全局可达最远位置maxPos遍历一遍就能得出答案。第四步给出代码并分析复杂度时间O(n)空间O(1)。第五步如果你想让面试官眼前一亮可以补充一句“这道题的end触发性更新本质上是把一次跳跃看成一个阶段每个阶段结束时把边界延伸到maxPos所以算法也叫BFS的压缩版本。”最后一条是杀手锏。你想想跳跃游戏每跳一次是一层覆盖范围内的所有点都是该层的节点而maxPos记录的是下一层能到达的右边界。这不是BFS是什么只不过BFS需要队列这里压缩成两个变量就够了。6.4 我自己刷题时的三个心得心得一别急着写代码。我第一遍做这道题时上来就想“最小步数DP”写了三四十行代码提交后还沾沾自喜。结果后来看官方题解发现一个O(n)的贪心就能解决当场有点脸热。从那以后凡是看到“最值”类题目我都会先花两分钟想想“有没有贪心性质”再决定要不要上DP。这个习惯帮我省了很多时间。心得二边界要一上来就想清楚。n 1返回0、循环到n-2而不是n-1、maxPos初始化为0而不是nums[0]这三个点只要错一个答案就是错的。我建议把这三条写成注释放在代码旁边防止以后回来看的时候又踩一遍。心得三拓展题一定要做。做完了跳跃游戏2我建议立刻去做LeetCode 55跳跃游戏、LeetCode 1024视频拼接和LeetCode 45的变种“如果要求输出路径”。输出路径的解法是在贪心更新step的时候记录下当时选择的下标然后根据记录的路径反向追踪。代码也不复杂vectorint jumpPath(vectorint nums) { int n nums.size(); int step 0, end 0, maxPos 0, chosen 0; vectorint path; for (int i 0; i n - 1; i) { if (i nums[i] maxPos) { maxPos i nums[i]; chosen i; } if (i end) { path.push_back(chosen); end maxPos; step; } } return path; }这样路径就记录在path里了。面试时如果能把这个变种也答出来基本等于告诉面试官“这道题我不仅是会背是理解了”。7. 写在最后贪心这条路上的“先证明后放心”回头再看跳跃游戏2这道题它最值得学习的不是那几行代码而是“为什么贪心可以用”的整套思考过程。我第一次做这道题时即使看了题解心里也一直犯嘀咕凭什么扫一遍就敢说这是最优解后来把反例、证明、暴力验证全走了一遍才彻底放下心来。这也是我觉得贪心算法最迷人的地方——它看起来特别“投机取巧”但背后有严谨的数学逻辑兜底。你写的那几行代码看似只是简单地取最大值、更新边界实际上每一步都在证明“不存在比这更优的路径”。这种“一眼看穿问题本质”的能力才是刷题最该练的东西。如果你现在正在准备面试或者正在刷leecode100的题单我建议你把这道题和背包问题放在同一天看。跳跃游戏2代表“连续决策空间的贪心”分数背包代表“增量选择空间的贪心”0/1背包代表“离散组合空间不能贪心”。三个题摆在一起你对贪心算法的理解会有一个质的提升。最后分享一个小技巧刷题时不要只追求AC试着在代码旁边写一行注释说明这个变量为什么这么更新那个边界为什么这样处理。写不出来的地方就是你还没真正理解的地方。我自己的代码里end maxPos这行旁边的注释写的是“这一跳最大的收益已确定开始下一跳”。写完这句话之后这道题我再也没错过。