如果你刷过力扣第 45 题大概率会经历一段挺折磨的心路历程读完题觉得这也太简单了——每次都跳到能跳的最远位置次数不就最少了然后自信提交答案错误瞬间开始怀疑自己是不是理解错了题。说实话这道题单独看只是一道中等难度题但它经常出现在大厂算法面试的第二轮甚至第三轮。原因不是代码难写恰恰相反完整解法不到十行。它真正考察的是一种特别容易被忽略的思维转变把“跳跃次数”理解成“覆盖区间的扩展批次”。如果你能把这个转变讲清楚面试官基本就满意了代码只是顺便的事。这篇文章我不打算只贴一份能通过的代码。我会把这道题掰开揉碎从为什么“每次跳最远”是错的到两个关键变量 current_end 和 farthest 到底在干嘛再到循环边界为什么一定要写 range(n-1)最后聊聊它和一整类区间贪心问题的关系。不管你是准备面试还是单纯刷题提升熟练度这篇都值得看完。1. 为什么每次跳最远不是正确答案题目精读与直觉陷阱1.1 题目到底在问什么先原原本本看一遍题。给定一个非负整数数组nums你最初位于下标0。nums[i]表示你在下标i上最多可以跳多远。目标是用最少的跳跃次数到达最后一个下标。注意三个关键字“最多”而不是“必须”你在位置i可以跳1到nums[i]之间的任意整数步。“最少跳跃次数”是唯一目标题目不要求你输出跳跃路径。“测试用例保证可以到达”这句话在 LeetCode 45 里是明确给出的后面我们会聊到如果没有这个保证该怎么改。示例是nums [2,3,1,1,4]答案是2。因为可以从下标 0 跳到 1再从 1 直接跳到 4正好两跳。但如果你从 0 尽全力跳到 2那就只能从 2 到 3再从 3 到 4变成三跳。这里就出现了一个特别容易让人轻敌的点很多人觉得“我每次尽量跳远用的步数自然最少”。这在某些数组里是对的在某些数组里是错的。它并不是这道题的正确策略而是一个需要被推翻的直觉。1.2 一个反例推翻最远跳策略继续用示例[2,3,1,1,4]推演一下采用“每次都跳最远”从 0 出发nums[0]2最远跳到下标 2。在下标 2 处nums[2]1跳到下标 3。在下标 3 处nums[3]1跳到下标 4。全程用了 3 跳。正确的最优解只要 2 跳第 1 跳从 0 到 1此时nums[1]3第 2 跳直接从 1 到 4。问题出在哪最远跳的策略只盯着“当前这一步能蹦多远”却完全没有评估“这一步落下去之后下一步还能延伸多远”。位置 0 可以跳到 1 或 2虽然 2 更远但位置 1 的剩余潜力nums[1]3远高于位置 2nums[2]1。再举一个看着更细碎的例子[1,2,1,1,1]。从 0 出发没得选只能先到 1。在位置 1 可以跳 1 或 2。如果选择跳到更远的 3后面只能一步步挪答案是 3 跳如果选择跳到 2最后也还是 3 跳。这个例子里策略分不出高下。而[3,1,2,1,4]这个例子更有意思从 0 最远跳到 3然后从 3 到 4只要 2 跳如果从 0 跳到 1再从 1 到 2最后从 2 到 4反而要 3 跳。在这个数组里“最远跳”恰好是对的。三个例子摆在一起就能看出来最远跳策略时灵时不灵。真正正确的判断依据不是单次跳跃的距离而是这一步之后整个“可达范围”能扩展多远。这就需要换一种观察角度。1.3 正确的观察方式区间而非单点把思维从“落在哪个点”切换到“一片连续区间”。假设现在已经跳了k次那么你能到达的位置一定不是一个一个孤立的点而是从起点开始的一段连续区间[0, x]。原因很简单因为每次跳跃的距离可以在1到nums[i]之间任意选择你能跳到的位置之间没有缝隙。如果某个位置p是可达的那么从起点到这个位置路径上的所有中间点要么是落点要么是你本可以提前停下的位置总之也都在可达范围内。这个“可达区间连续”的性质是整道题最关键的观察。有了它问题就可以重新表述为当前跳跃次数下我们能覆盖[0, current_end]现在要把这个右边界向右推推到什么时候能覆盖终点n-1就算结束。这样做的好处是我们彻底不需要纠结“下一跳具体落在哪个点”了。因为落在区间内的任意一个点都在我们控制范围内。我们要做的只是把这个区间内所有点作为起点挨个看一眼它们能跳多远取一个最大值然后在需要开启下一次跳跃时把区间右端一次性推到那个最大值。这就是贪心算法的全部内容。2. 贪心策略的推导从站内全部站点到下一跳最远扩展2.1 两个关键变量各自的职责基于上面的区间视角代码里只需要两个变量很多人就是死在这两个变量上farthest在当前已走过的区间里所有位置能到达的最远下标。它代表“如果我现在立刻再跳一次最多能到哪”。current_end当前这一跳所能覆盖的区间边界。也就是在当前跳跃次数下不额外再跳我能走到的最远下标。我用一句话区分它们current_end是“现在不用跳也能待的区域边界”farthest是“我把区域内所有点考察一遍后下一步能摸到的天花板”。算法从下标 0 开始一路向右遍历每一步只做两件事用当前位置的跳跃潜力刷新farthestfarthest max(farthest, i nums[i])。检查i是否已经走到了current_end。如果走到了说明当前这一跳覆盖的所有位置都考察完了再想往右走就必须开启新的一跳。此时把steps加 1并把current_end更新为farthest。想清楚这个“被迫才跳”的惰性更新就抓住了这道题的灵魂。我们不是每到一个位置都立刻跳而是能不动就不动等到当前覆盖范围实在到头了才统一结算一次跳跃而且一跳就跳到理论最远的位置。2.2 手推一遍示例数组看区间推进用[2,3,1,1,4]手动推一遍。初始状态steps 0current_end 0farthest 0。inums[i]更新 farthesti 是否等于 current_endstepscurrent_end02max(0, 02)2是1213max(2, 13)4否1221max(4, 21)4是2431max(4, 31)4否24循环遍历到i 3也就是倒数第二个元素就结束了返回答案是 2。注意一个很有意思的细节在i1时farthest已经被更新成了 4代表我们其实已经知道“下一跳可以直接到终点”。但steps并不会在这里立刻加 1而是要等到i2真正走到当前覆盖范围的边界时才把这一跳结算掉。这种“信息先到次数后计”的模式正是贪心算法里最常见的写法之一。它看起来有点绕但好处是绝对不会多计次数。因为只要当前覆盖区间还能继续往前走就说明还没到必须跳的时候这时候跳是浪费。再推一个[1,1,1,1]的极端数组inums[i]更新 farthesti 是否等于 current_endstepscurrent_end01max(0, 1)1是1111max(1, 2)2是2221max(2, 3)3是33答案 3和直觉完全一致每一步只能平移一格n - 1 3次没得跑。这个例子虽然平凡但很适合用来验证代码逻辑有没有把边界记错。2.3 为什么贪心在这里就是全局最优这是面试必考的一问你凭什么说“每次在边界处把区间推到 farthest”就是全局最少次数核心依据还是连续性。假设当前跳跃次数是k当前覆盖区间是[0, current_end]。在这个区间内任意一点我都能到达都能作为下一次跳跃的起点。那么下一跳无论怎么跳它的落点归属范围都不可能超过farthest max(j nums[j])其中j遍历[0, current_end]。这个式子是所有可行策略的公共上界。也就是说不管你用什么策略你第k1跳最多只能把覆盖范围推到farthest没有哪个策略能比这更远。而我们恰恰把区间推到了farthest。这意味着在第k1跳这个环节我们的选择不劣于任何其他选择。把同样的话对k 0, 1, 2, ...重复每一步都不劣于别人最终的总次数自然最优。如果你觉得这个证明还是有点抽象我用大白话翻译一遍你在当前能到达的所有位置上仔细比较了它们各自的下一步潜力挑出了潜力最大的那个。其他任何策略能选的无非也是这些位置所以不可能比你选得更远。既然每一轮都做到了“最远”那总次数当然最少。这个证明逻辑很干净建议面试时按这个顺序讲面试官能立刻抓到重点。3. 代码实现与循环边界的细节3.1 核心代码一份能跑的 Python 解法上面思路转化成代码非常短class Solution: def jump(self, nums: List[int]) - int: n len(nums) if n 1: return 0 steps 0 current_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i current_end: steps 1 current_end farthest return stepsn 1的判断其实可以省略因为n 1时range(n - 1)是空范围循环根本不会执行steps保持 0。但加上它有两个好处第一代码自解释性更强读的人一眼就能看出你考虑过空跳的情况第二防止在改写成 while 循环时不小心把边界条件弄丢。所以我还是建议显式写出来。就这段代码没有任何花哨的东西但它包含了这道题所有的考点farthest的正确计算、current_end的延迟结算、以及循环边界range(n - 1)。3.2 为什么循环写到 n-1 而不是 n这个问题几乎必问也是新手最容易翻车的地方。如果循环写成for i in range(n)那么在i n - 1也就是已经站在终点的那一轮假如current_end恰好等于n - 1就会触发i current_end分支steps会被多加一次。为什么循环到n - 2就够了因为n - 1这个位置是终点它永远不需要作为跳跃起点。我们要考虑的所有“起跳位置”最多只到n - 2。位置i能影响的只是i nums[i]也就是它作为起点能把范围推到多远而终点本身不需要再推任何范围。换个更严谨的说法每次steps的增加都发生在i current_end且current_end n - 1的时刻。也就是说只有当当前覆盖范围确实还没覆盖到终点、必须跳一次的时候steps才会加。循环到n - 2时所有可能的临界位置都已经走过一遍了如果终点还没被覆盖那么在某个i n - 1的位置一定还会触发一次结算把current_end推到 n - 1。如果终点已经被覆盖那么后面根本不会再触发结算循环自然结束也不会多加。所以结论是range(n - 1)不多不少恰好遍历完所有需要考察的起跳点。3.3 提前退出、变量命名和两个常被问的写法变体网络上有一种写法会在i current_end时加一个提前退出判断for i in range(n - 1): farthest max(farthest, i nums[i]) if i current_end: steps 1 current_end farthest if current_end n - 1: break实际上不加这个 break 也对。原因前面已经说了一旦current_end n - 1后面所有i都小于current_end永远不会再进入i current_end分支。不过加上 break 能提前结束循环在语义上也更明确我已经能覆盖终点了后面不用看了。两种写法面试官都能接受我个人习惯加上因为它能让你在面试时很自然地说出那句关键的话“现在这一跳已经能覆盖到终点了所以结束。”还有一个常见的疑问是变量命名。有人用end有人用border有人用max_pos。我建议统一用current_end和farthest因为这两个名字直接对应“当前覆盖边界”和“最远可达位置”在跟面试官沟通时几乎不需要额外解释。如果看到用 while 循环维护起点位置不断内跳的写法也别慌。那种写法的本质是每跳一次就真实地移动到一个“最佳落点”然后在以该落点为起点的小区间里继续找下一跳落点。它也能得到正确答案但代码复杂度更高容易在边界条件上栽跟头。我更推荐区间扫描写法因为逻辑更接近这道题的本质。3.4 复杂度分析和为什么 DP 不是首选代码是单层循环每个位置最多访问一次时间复杂度O(n)额外变量只有几个空间复杂度O(1)。很多人在面试时会先说一个动态规划解法设dp[i]表示跳到下标i的最小次数状态转移为dp[i] min(dp[j] 1)其中0 j i且j nums[j] i。这个写法非常直白初始化dp[0] 0其余为无穷大算完返回dp[n-1]。但它有一个明显的问题对每个i都要往左遍历所有可能的j最坏情况下时间复杂度是O(n^2)空间O(n)。当n是十的六次方级别时直接超时。相比之下贪心解法把二维的扫描压缩成了一维并且完全不依赖 DP 数组。所以面试里更推荐的路径是先提一嘴“这道题虽然可以 DP但我会用更优的贪心”然后直接进入区间扫描。这样既展示了你对多种解法的了解也不会浪费时间写一个注定不是最优的版本。4. 最容易翻车的边界情况与面试追问4.1 输入长度为 1别把答案算成 1nums [0]时你已经站在终点了答案应该是 0。如果你不写n 1的保护在某些 while 写法的版本里可能出问题。比如有人习惯先把steps初始化为 1想着“跳了一次才到某个位置”结果长度为 1 时答案直接变成 1。这个错误很低级但在面试压力下经常出现。而且很多时候不是因为你不会而是因为你没把“起点就是终点”这个特殊情况放在一个显眼的位置检查。一个不出错的小技巧是不管用什么思路开篇第一行就写长度判断。它用不了 5 秒钟但能帮你省掉一大类边界错误。4.2 第 55 题和第 45 题的真正区别LeetCode 55 题“跳跃游戏”问的是能不能到达终点它只需要一个变量max_reach记录当前最远可达位置def canJump(nums): max_reach 0 for i in range(len(nums)): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach len(nums) - 1: return True return False45 题是在“保证可达”的前提下求最少次数所以额外需要current_end来把跳跃分成“批次”。你可以把 55 理解成只记录“区间右端最大能到哪”把 45 理解成在记录这个右端的同一时间还记录了“当前这一批区间是哪一跳产生的”只有在批边缘才结算次数。这两个题目在面试里经常连着问或者作为同一轮的两道递进题。如果你能主动说出它们的区别比如“55 只需要判断边界能不能继续推进45 需要维护一个额外的区间端点来分批计数”面试官会认为你确实在理解问题而不是背题。4.3 面试官让你证明贪心时怎么讲面试最怕的就是面试官追问“你凭什么说贪心解是最优的”你愣住。我建议按下面这个顺序讲逻辑完整又不会太啰嗦可达区间具有连续性。能到最远点x那么[0, x]之间所有点都能到。当前区间是[0, current_end]下一跳所有可能的起点都在这段区间里。下一跳能到达的最远位置是farthest max(j nums[j])任何策略都不可能超越这个上界。我们恰好每跳都把区间推到farthest所以每一跳都不劣于任何策略。每一跳都不劣于别人总跳数自然最少。讲的时候最好同时拿[2,3,1,1,4]在纸上画一画把第 1 跳区间[0,2]标出来再把farthest4标出来让面试官看到一个具体的可视化过程。还有一个经常被追问的点“你不怕中间跳到某些位置会漏掉更优路径吗”回答是否定的。因为当我们把区间直接推到farthest时中间所有点依然都在覆盖范围内它们没有被漏掉只是不需要再额外安排跳跃。下一次如果要从中间某个点出发也不会受到任何影响。4.4 current_end 更新时机写反会怎样这是我见过最典型的错误写法远看很像正确答案一提交就错# 错误示范 for i in range(n - 1): if i current_end: steps 1 current_end farthest farthest max(farthest, i nums[i])区别只在于先更新了current_end再更新farthest。看起来只是两行换了个顺序实际逻辑完全崩坏。因为在i current_end的这轮里你把current_end更新成了还没有吸收当前i贡献的旧farthest等于漏掉了这个边界点本身的跳跃潜力区间扩展会偏小。用[2,3,1,1,4]跑这个错误版本第一轮current_end被设成了 0后面所有i都不可能再等于 0最终steps只加了 1 就结束了答案错得离谱。所以请把顺序焊死先刷新farthest再判断是否需要结算跳数、更新current_end。这个顺序背后是因果逻辑你必须先收集完当前区间里所有点的最优信息才能决定下一跳能跳多远。5. 举一反三区间覆盖问题的通用套路5.1 把题目改成不可达返回 -1LeetCode 45 明文保证了可达但面试官随时可能去掉这个条件。如果输入不保证可达怎么改思路是在“走到current_end边界”时判断一下farthest有没有比current_end更大。如果没有说明当前覆盖区间内的所有点都跳不出去后面任何一个点也都到达不了直接返回 -1def jump_with_invalid(nums): n len(nums) steps 0 current_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i current_end: if farthest current_end: return -1 steps 1 current_end farthest return steps这个改造只需要加一个 if 判断非常自然。在面试里能主动写出这个版本说明你对“区间卡死”这个概念有真实理解而不是只会背模板。5.2 视频拼接与最小区间覆盖同一个贪心内核LeetCode 1024 题“视频拼接”给你若干视频片段区间[start, end]问最少选几个片段能覆盖[0, time]。你可能会觉得这题和跳跃游戏八竿子打不着实际上它们的贪心模型完全一致。视频拼接里你先把所有片段按起点排序然后维护current_end当前已选片段能覆盖到的最右端。farthest在所有起点不超过current_end的片段里能延伸到的最远右端。每当遍历完符合条件的片段发现已经到达current_end时就贪心地选一个能延伸到farthest的片段次数加一current_end更新为farthest。只看这段描述它和跳跃游戏没有任何区别。差别只有一个跳跃游戏的数组天然有序从下标 0 一路向右不需要排序视频拼接输入的区间是乱序的所以要先按 start 排序。把这个共同点讲给面试官听对方会觉得你做题不是一道一道做而是按模型在做。类似的还有“最小区间覆盖”模板题给你一堆区间和一个目标长度问最少选几个区间能覆盖目标。用的还是这一套变量只是排序规则和边界判断略有调整。5.3 贪心不灵的场景什么时候该老老实实 DP贪心虽然高效但不是万能。硬币找零里如果面额是[1,3,4]要找零 6贪心会先拿一个 4再拿两个 1一共 3 枚最优解却是两个 3只要 2 枚。这个例子说明一旦局部选择会改变未来可选项的集合贪心就可能失效。跳跃游戏为什么特殊因为它的未来选择空间不会被“当前落点”破坏。无论你落在当前区间的哪个点最后能扩展出的farthest上界都是一样的取 max 就代表你实际上遍历了所有可能落点。而在硬币问题里你拿了一个面额较大的硬币就消耗了一定的总额度这个消耗会影响后续能拼出的组合局部最优和全局最优之间存在冲突。所以做题时建议先问自己一个问题“这一步的选择会不会永久排除某些未来的可能性”如果会多半要 DP 或搜索如果不会只是把某个上界不断向外推那贪心有戏。跳跃游戏明显属于后者。还想让这个系列刷得更扎实的话可以把 LeetCode 55、45、1024 放在同一天做。55 练最基础的可达性判断45 练区间分批计数1024 练排序和贪心的结合。三题做完区间覆盖类问题基本就通了一半。刷了这么多年算法题我的体会是45 题值得你把它收藏起来反复看不是因为它代码长而是因为它提供了一个特别经典的思维模型——用“连续性”把动态决策压缩成贪心。下次再遇到“最少需要几批才能覆盖这么远”的问题先画当前覆盖区间再算区间内所有点的下一步扩展很多看上去很难的题会瞬间变简单。最后分享一个面试小技巧写代码前不要急着动键盘先在白板上画出[2,3,1,1,4]的区间推进图明确标出current_end和farthest。让面试官看到你对贪心边界的理解远比你十分钟默写代码更有说服力。这道题真正想淘汰的从来不是背不出代码的人而是说不清“为什么不能每次都跳最远”的人。