我第一次在LeetCode上碰到跳跃游戏时第一反应是建图、跑DFS把所有路径枚举一遍看看有没有一条能摸到终点。相信很多人和我一样被跳跃这个词带偏了以为这是个搜索问题。实际上LeetCode 55题的正解是贪心算法而且它简单到你只需要维护一个变量当前能到达的最远位置。这篇文章想做的不是把AC代码丢给你而是把跳跃游戏系列重点是55、45两道贪心题背后的模型讲透为什么要维护最远可达位置为什么局部最优能推出全局最优循环边界怎么写才不会被边界用例卡住顺带也会把系列里的其他变体过一遍帮你建立一个哪种题该上贪心、哪种题该上DP的判断框架。适合正在刷LeetCode准备面试、或者刷到跳跃系列总觉得差一口气的同学。1. 把跳跃游戏翻译成区间覆盖贪心直觉从哪来1.1 从一道真题说起判断能否到达终点题目长这样给定一个非负整数数组nums你最初位于数组的下标0处。数组中的每个元素代表你在该位置可以跳跃的最大长度判断你是否能够到达最后一个下标。两个经典例子nums [2, 3, 1, 1, 4]输出true。你从0跳1步到1再从1跳3步直接到4。nums [3, 2, 1, 0, 4]输出false。不管怎么跳都会被下标3的0卡住永远到不了4。第一题大多数人都能凭直觉做出来第二题才是关键为什么明明前面的数都很大却还是到不了终点因为下标3的0像一堵墙切断了通往后面的路。这个墙的视角恰恰是贪心解法的入口——我们不需要关心每一步具体跳到哪只需要知道目前能覆盖的最远范围有没有越过这堵墙。我强烈建议你先把题目自己动手做一遍再往下看。因为这道题有一个很反直觉的点它表面上像是在问有没有一条路能走通但真正高效的解法不关心路径只关心范围。想通这一点整个系列就通了一半。1.2 第一反应陷阱DFS、BFS和DP为什么都绕远了我在面试和社区答疑里见过太多次这个场景候选人一看到跳跃立刻开始建图每个下标是一个节点从i到i1 ... inums[i]连边然后跑DFS或BFS。DFS的思路是从0出发递归尝试每一种跳跃步数看能不能碰到n-1。确实能过小数据但最坏情况下每个位置可以跳出去很多分支递归层数和分支数叠加复杂度接近指数级。BFS也一样每个位置入队出队最坏O(n^2)个边要遍历。还有一种常见做法是动态规划定义dp[i]表示下标i是否可达然后从前往后推。每次更新dp[i]时要回头扫描前面所有能跳到i的位置复杂度O(n^2)空间O(n)。能过但笨重。这三种思路的共同问题是它们默认跳跃是一个需要探索路径的离散决策。但题目问的是能否到达不是怎么到达。这就好比你想知道北京和上海之间有没有直达铁路结果你非要把每一站都枚举一遍。其实只要查一下这条线路的覆盖范围就够了。我没有任何贬低DFS或DP的意思它们在后边的跳跃游戏III、VI里反而是正主。但在这道题上它们都绕远了——原因是题目里每个位置能跳的最大长度天然形成了一个连续区间而区间问题最怕的就是枚举细节。1.3 一个生活类比顺风车只会越开越远想象你在一列只能往前开的通勤班车上每个停靠站写着一个数字这个站点出发后最多还能往前开几站。你不需要知道到了某个站后具体坐哪辆车你只需要知道一件事——从所有已到达的站点里最远能把自己接力到哪个站。这个最远接力点有一个关键性质它是单调不减的。一旦你到达了第5站那么第1到第4站必然都已经到达过因为车只能一站一站往前开如果第1站能接力到第8站那么整个1到8站全都进入了可达范围。所以一路上你只需要不断刷新最远接力点如果它覆盖到终点就成了。这其实和区间合并是同一个直觉把所有可达位置看成一段不断向右延伸的区间题目变成了这段区间最终能不能覆盖到 n-1。一旦把视角从选路径切换成扩区间贪心解法几乎是白送的。2. 最远可达位置的递推与证明一趟扫描的关键2.1 状态定义与循环边界的反直觉点前面说了一堆直觉现在落到代码上。定义max_reach表示当前从起点出发能到达的最远下标。初始时max_reach 0因为人就在0号位置。然后我们从左往右遍历不断用当前位置能跳到的距离去刷新它def canJump(nums): n len(nums) max_reach 0 i 0 while i max_reach and max_reach n - 1: max_reach max(max_reach, i nums[i]) i 1 return max_reach n - 1这个写法看起来简单但里面藏着一个最容易写错的地方while i max_reach而不是while i n。为什么因为max_reach代表的是可达范围。如果循环到某个位置i时i已经严格大于max_reach说明这个位置根本到不了它后面的位置也统统到不了。此时再往后遍历没有任何意义直接返回false。很多人的错误代码长这样# 错误写法不管到不到得了都一直往后扫 def canJump(nums): max_reach 0 n len(nums) for i in range(n): max_reach max(max_reach, i nums[i]) return max_reach n - 1这个写法在nums [0, 2, 3]上会返回false正确但在nums [0, 1, 0]上也会返回false碰巧正确。真正危险的是nums [0, 5, 0]按错误写法max_reach在i1时会被错误地更新成6于是返回true而实际上你连下标1都到不了。问题就出在不可达的位置不应该参与计算但for循环没有屏蔽它。2.2 为什么局部取max能推出全局可达很多同学就算代码写对了心里也是虚的面试官一追问为什么贪心是对的就卡壳。这里我给一个严谨但不复杂的归纳证明。假设我们处理到下标i时max_reach是区间[0, i-1]内所有已访问可达位置能延伸的最远距离。现在位置i本身是否可达如果i max_reach说明i在可达区间内那么i nums[i]这个候选值就应该参与竞争于是max_reach max(max_reach, i nums[i])更新后的max_reach就是包含位置i之后的所有可达位置的最远延伸。数学归纳法走一遍基准情况max_reach 0显然成立递推步骤上面证明了所以循环结束时max_reach就是从起点出发真正能到的最远距离。这里隐含着一个非常关键的单调性max_reach永远只会不变或变大绝不会回退。这个单调特质正是贪心能用的基石——每个位置的贡献是独立的、可叠加的前面的选择不会让后面的能力变小。就像接力赛每一棒的发挥只会让总成绩更好不会拖累下一棒。2.3 三种常见错误写法与反例我总结了三个高频错误每个都是我实际见到过的你自查一下第一个错误是循环范围不对。有人把while i max_reach写成for i in range(n)导致不可达位置参与计算前面已经举例。修法是在循环开头判断if i max_reach: return False或者直接用while控制范围。第二个错误是含义理解偏。有人把nums[i]当成必须跳的步数于是用max_reach max(max_reach, i nums[i])时下意识觉得要先走到某个中间位置才能跳。其实nums[i]是最大步长你可以跳1到nums[i]之间的任意步数所以i nums[i]只是把候选范围一次性全部并入可达区间。第三个错误反而是想太多试图记录具体路径。有人会开一个pre数组或者递归回溯把能否到达这种判定题做成了构造路径题。一旦这么做时间和空间复杂度都上去了而且代码很难写对。记住这题只要一个整数变量。3. 跳跃游戏 II最少跳跃次数的区间推进法3.1 从能否到达到最少几次题目变了什么LeetCode 45题在55题基础上加了一个问题假设你总是可以到达数组的最后一个位置求最少需要跳几次。多了一个最少贪心策略就得升级。55题里我们只需要维护一个全局最远距离45题里我们需要知道的是在当前这一跳能覆盖的范围内下一跳最多能延伸到哪。等到当前范围走完时再跳一次把边界推进到下一跳的最远位置。这其实是一个非常经典的区间推进模型把整个跳跃过程切成若干段区间第0段是初始位置第1段是第0段内所有位置一跳能覆盖的范围第2段是第1段内所有位置一跳能覆盖的范围……每次从一段跳到下一段就消费一次跳跃次数。为什么这样能保证最少因为每一段内所有位置都只需一次跳跃就能到达。如果你能用1次跳到某个位置就绝不能用2次——能少跳就不少跳。所以贪心在这里的表述是每次跳跃都把下一跳的覆盖范围推到当前段能达到的最大值最大化每次跳跃的收益。3.2 curEnd与curFar双指针推演全过程代码模板是双指针cur_end表示当前这段跳跃的右边界也就是我现在这一跳能到达的最远位置cur_far表示在扫描cur_end之前所有位置时累计发现的下一跳能到达的最远位置。def jump(nums): n len(nums) if n 1: return 0 jumps 0 cur_end 0 cur_far 0 for i in range(n - 1): cur_far max(cur_far, i nums[i]) if i cur_end: jumps 1 cur_end cur_far if cur_end n - 1: break return jumps拿nums [2, 3, 1, 1, 4]推演一遍步骤inums[i]cur_far更新i cur_endjumpscur_end102022是0012213max(2, 134)4否12321max(4, 213)4是2224431max(4, 314)4否24扫到cur_end4 n-1循环提前退出返回2。这里的路径是0跳到11跳到4正好2次。注意一个细节当i1时我们发现了下一跳能到4但没有立刻跳而是先记账。真正触发跳跃是在i撞上当前的cur_end时。这种先记账、后结算的模式是区间推进法的灵魂。3.3 为什么循环只走到 n-2 以及跳跃计数的时机很多人在45题上纠结一个问题为什么for i in range(n - 1)不遍历最后一个位置原因很简单当你已经站在最后一个位置时不需要再跳了。“跳数”记录的是从起点到终点需要消费几次跳跃而不是一路上经过的所有位置里有多少个可以跳。举个例子nums [1, 2]从0跳1步到1答案1次。如果用range(n)遍历到i1时又会触发一次跳跃算出2次错误。所以遍历范围必须排除最后一个下标。还有一个容易踩的坑nums [0]或者nums [1]。数组长度为1时你已经在终点了最少跳数应该是0。上面的代码第一行if n 1: return 0就是在处理这种情况。千万别漏漏了会在[0]上返回奇怪的结果。另外如果你把cur_end n - 1的提前break去掉代码也能跑但会多做无用功。保留它既省时间也是给面试官看的我理解了什么时候可以停的信号。4. 跳跃游戏系列全览哪些题能用贪心哪些必须上别的武器4.1 系列其他题目的分类可达性、步数、得分、路径约束LeetCode上以跳跃游戏命名的题不止55和45还有1306、1340、1345、1696、1871等。很多人以为整个系列都是贪心结果一刷发现有的根本贪不动怀疑自己学了个假算法。我按考察点把它们分个类题号核心问题推荐解法贪心可用55能否到达终点贪心维护最远可达是45最少跳跃次数贪心区间推进是1306从起点能否跳到目标值相等的位置BFS/DFS否1340相邻且更低的石头上跳跃求最多访问数排序 DP / 记忆化搜索否1345每次可跳到相邻位置或同值位置求最短步数BFS否1696每次最多跳k步求到终点的最大得分DP 单调队列部分思想1871每次可在区间内跳跃判断可达DP 前缀和优化否这张表告诉我们跳跃游戏是一个家族不是一种解法。55和45之所以能用贪心是因为跳跃范围是连续区间这个结构让局部最优可以直接累积成全局最优。而1306和1345跳到了图的模型必须搜索1696的目标变成了得分最大当前选择会影响后续收益必须DP。4.2 跳跃游戏 VI贪心思想如何演变成单调队列DP挑1696题展开说一下因为它特别有意思。题目要求从下标0出发每次可以跳到i1到ik之间的任意位置每个位置有一个得分求到达最后一个位置的最大总得分。直觉上你想每次都跳到可选范围内得分最高的位置但这是错的。因为当前跳到的位置会决定下一轮的可选窗口局部最高分会把你带进死胡同。比如nums [1, 100, 1, 1, 1, 100]如果贪心地从0跳到1100分下一步可选窗口是2到3可能错过后面更大的100。正解是动态规划dp[i] nums[i] max(dp[j])其中j在[i-k, i-1]范围内。为了快速求窗口内dp[j]的最大值用单调队列维护一个递减的下标序列def maxResult(nums, k): from collections import deque n len(nums) dp [0] * n dp[0] nums[0] q deque([0]) for i in range(1, n): while q and q[0] i - k: q.popleft() dp[i] dp[q[0]] nums[i] while q and dp[q[-1]] dp[i]: q.pop() q.append(i) return dp[-1]为什么队列尾部要弹出较小的dp因为新下标更大、更靠右在后续窗口里存活时间更长如果它的dp还比队尾大那么队尾那个元素永远不会再被用到——这就是贪心里的淘汰策略。所以1696正解不是贪心但优化手段里带着贪心的淘汰灵魂。4.3 贪心还是DP一张表看清判断依据我总结了一个快速判断口诀问可行性看覆盖问路径上搜索问最值想DP问次数看贪心能不能归纳成立。更具体一点如果当前选择不会改变你未来的能力边界55、45里跳得远只会让边界变大不会变小贪心大概率成立。如果当前选择会在收益和未来可达性之间做权衡1696里的得分会影响后续大概率要DP。如果问题本质是图上的连通性1306、1345BFS/DFS是正解别硬套贪心。提示面试时如果拿不准先把暴力或DP思路说出来再尝试用贪心优化。面试官更看重你能不能证明贪心成立或者能不能意识到贪心不成立而不是直接猜对方法。5. 实战验证边界用例、错误表现与一套通用模板5.1 必须跑一遍的边界用例集合我在刷题时习惯把边界用例单独存一个文件每次写完就批量跑。跳跃游戏系列的边界用例我建议至少覆盖下面这些用例55题结果45题结果说明[0]true0已经站在终点[1]true0同上[0, 1]false题目保证可达则不会出现起点就是0跳不出去[1, 0, 1]false同上跳到1后被卡死[2, 0, 0]true1一步直达终点[1, 2]true1只跳一次验证45别多算[2, 3, 1, 1, 4]true2标准正例[3, 2, 1, 0, 4]false题目保证可达则不会出现标准反例[4, 4, 0, 0, 0, 1]true2最远点不是最优路径[4, 4, 0, 0, 0, 1]这个用例特别能说明只看 max_reach 就够从0能跳到44又能跳到5所以可达。但如果你尝试记录具体路径会发现从0先跳到44跳1步到5是唯一解如果跳过头去了1、2、3反而因为那边是0而卡住。贪心算法不在乎这些——它只关心可达范围有没有覆盖终点。5.2 剪枝与常数优化从正确到高效55题的贪心已经是O(n)时间和O(1)空间理论最优。但仍有一些小优化值得了解第一提前返回。一旦max_reach n - 1立刻返回true不用再遍历后面的元素。这在终点很靠前的大数组上能省不少时间。第二对45题可以在cur_end n - 1时立刻break。因为后续遍历不会再改变跳跃次数了提前退出既省时间又避免边界出错。第三如果数组元素几乎都很大45题每次cur_far max(cur_far, i nums[i])其实可以安全地写成cur_far max(cur_far, i nums[i])然后判断这已经是常数级别的操作再做别的优化意义不大。还有一个细节Python里while i max_reach比每个循环都判断if i max_reach要快一点而且语义更清晰。我自己更喜欢用while版本写55题。5.3 一份同时兼容55题与45题的贪心模板我通常会把两个题合并成同一个模板记忆因为它们的结构高度相似。55题可以看作只问能不能到45题是能到的情况下最少几步。def solve(nums, need_steps): n len(nums) if n 1: return 0 if need_steps else True jumps 0 cur_end 0 farthest 0 for i in range(n - 1): if i farthest: return -1 # 不可达 farthest max(farthest, i nums[i]) if i cur_end: jumps 1 cur_end farthest if cur_end n - 1: break return jumps if need_steps else (cur_end n - 1)这个模板同时处理了不可达和可达但需要最少步数两种情况。farthest在55题里等价于max_reach在45题里等价于cur_far。区别只在最终结果的定义。我建议你刷题时先背这个模板然后尝试自己推导cur_end和farthest的语义直到能不看代码口述出每一步的含义。到了那个程度这种贪心题基本不会翻车。6. 面试与刷题中的实战经验什么时候放心用贪心6.1 三条判断贪心适用性的经验法则怎么快速判断一道题能不能用贪心我这几年的经验浓缩成三条第一看题目要求的是可行性最少次数最大覆盖这类单一目标而不是输出所有方案或输出具体路径。单一目标通常意味着有一个可以单调维护的量。第二看当前选择会不会影响后续能力。跳跃游戏里你跳到哪里能跳多远只取决于当前位置的nums[i]而max_reach取的是历史最大值后面只会更大。这种选择不影响能力上限的结构贪心非常稳。第三试着反证。如果贪心策略是每步取局部最优那你可以尝试构造一个反例有没有可能这一步跳得最远反而让后面到不了终点在55题里答案是没有因为跳得远只会扩大可达区间。在1696题里答案是有因为跳得远可能错过低处的高分点。构造反例失败贪心基本成立构造成功果断上DP或BFS。6.2 系列刷题顺序与刻意练习方法如果你想把这个系列吃透我推荐按下面的顺序刷LeetCode 55先掌握最远可达位置的贪心模型。LeetCode 45理解区间推进和双指针记账。LeetCode 1306刻意切换成BFS/DFS打破贪心惯性。LeetCode 1345BFS求最短步数对比45的最少步数模型有什么不同。LeetCode 1696上DP 单调队列体会贪心淘汰在优化中的作用。LeetCode 1871DP 前缀和再来一轮优化。每刷完一道写一行笔记把它归入贪心/搜索/DP三个桶里。刷完整组你会很清楚地看到同一个跳跃题材因为约束条件不同解法会完全不同。这种对照记忆比单独刷几十道题都有效。6.3 面试中如何把贪心正确性讲得让面试官点头面试时千万别只丢出代码一定要讲清楚为什么这一步取最大是安全的。我的标准话术分三步第一定义状态用max_reach表示当前可达的最远下标它单调不减。第二证明维护正确性只要当前位置i max_reach它就可达那么它延伸出的i nums[i]也应该被纳入可达范围。取max就是在不断扩张可达区间的右端点。第三说明终点判定如果过程中max_reach覆盖到n-1说明可达如果遍历到某个位置发现i max_reach说明到不了了。这三步讲完面试官基本就会放过你。如果他还追问45题你就补上区间推进法的双指针表述cur_end是当前跳的边界cur_far是下一跳能到的最远位置到了边界就跳一次这就是最少次数因为每一跳都最大化了下一次的能力。我自己在面试里还习惯补一句如果题目不保证可达45题的代码要加一个不可达检测否则会在断崖数组上返回一个看似合理的错误答案。这句话通常能戳中面试官因为他可能正好想问你有没有考虑不可达的情况。刷完这组题我最大的体会是贪心算法不是靠直觉瞎猜而是靠定义单调量 归纳证明来建立信心。跳跃游戏系列恰好是练这套思维的最佳标本——它表面上有搜索、有DP的诱惑但只要你看穿区间覆盖的本质代码短得惊人。希望这篇把贪心模型的底裤扒干净的总结能让你下次见到跳跃游戏时少走几步弯路。