这道题是 LeetCode 55 跳跃游戏我几乎每次和同行聊贪心算法都会把它拎出来当第一个案例题面一句话就能读完难点却全藏在“能不能到达”这五个字里。给定一个非负整数数组nums每个nums[i]表示你在下标i处最多可以向前跳跃的长度初始位置在下标0问能否到达最后一个下标。表面看像个路径搜索题甚至可以直接用 DFS 把所有跳法枚举一遍。但真实的最优解只需要一个变量、一趟遍历核心就是维护一个“最远可达位置”。这篇文章我会把整套推演过程写清楚从最容易想到的暴力思路开始一步步走到贪心再贴出可直接运行的代码、边界用例、常见错误以及面试时怎么把这题讲得既快又稳。无论你是刚开始刷题、准备校招面试还是单纯想巩固一下贪心套路这题都值得你耐下心过一遍。1. 先把题目读透再决定用哪套算法1.1 原题面与两个经典示例题目给一个长度为 n 的非负整数数组每个位置上的数字表示“最大跳跃长度”。注意是“最大”不是“必须跳这么多”。你在某个位置可以跳 1 步、2 步直到这个最大值也可以不跳比如已经是终点。示例一nums [2, 3, 1, 1, 4]从下标 0 出发最大能跳 2 步。常见的走法是先跳到下标 1然后从下标 1 再跳 3 步直接落到终点下标 4所以结果是true。示例二nums [3, 2, 1, 0, 4]从下标 0 出发最大能跳 3 步你可以到下标 1、2 或者 3。但不管怎么走最后都会卡在下标 3因为下标 3 的值是 0一步都跳不出去所以结果是false。这两个示例把题目的核心矛盾暴露得很直接示例二最远能跳到接近终点的地方却在倒数第二步掉进一个“死点”。这也是很多人第一反应想到搜索而非贪心的原因。1.2 为什么这题在面试里出场率这么高面试官喜欢这题不是因为解法难恰恰是因为它“看起来简单做对不容易”。第一它考察你能不能把问题抽象成更简单的模型。会 DFS 的人不少但能在五秒内意识到“不需要真的模拟每一跳”的人比例就低多了。第二它考察边界感。数组长度是 1、某位置值为 0、最大跳跃长度远超数组长度这些情况都要覆盖。第三它是一整个题目家族的祖先跟后面的跳跃游戏 II、跳跃游戏 III 都有联系面试官可以顺着它无限扩展。2. 从暴力解法一路走到贪心2.1 暴力思路枚举所有走法先把最朴素的想法写出来。定义一个递归函数canJumpFrom(position)表示从position出发能否到达终点。def canJumpFrom(nums, position): if position len(nums) - 1: return True max_jump min(position nums[position], len(nums) - 1) for next_pos in range(position 1, max_jump 1): if canJumpFrom(nums, next_pos): return True return False这个写法逻辑完全正确但在最坏情况下会指数级爆炸。假设数组全是很大的数字每个位置会递归派生大量分支复杂度基本不可控。你拿它跑 LeetCode 的测试用例大概率会超时。这种暴力版本的价值在于它逼你把状态定义清楚。递归函数里每次跳多远是这道题最底层的动作。2.2 加一个缓存做成动态规划暴力超时的原因是有大量重复子问题。比如某个位置被多次作为中间点访问每次都要重新计算。用一个memo数组记录每个位置是否已确认能到达终点能把复杂度降下来。def canJump(nums): n len(nums) memo [None] * n memo[-1] True def helper(pos): if memo[pos] is not None: return memo[pos] max_jump min(pos nums[pos], n - 1) for next_pos in range(pos 1, max_jump 1): if helper(next_pos): memo[pos] True return True memo[pos] False return False return helper(0)这是“自顶向下 记忆化”的 DFS 版本实际复杂度大约是 O(n²)因为每个位置最多被计算一次每次要尝试它覆盖范围内的所有落点。内存也是 O(n)。想再进一步可以改成自底向上的 DP用一个dp[i]表示从下标 0 出发能否到达下标 i然后遍历每个可到达的位置把它能延伸到的范围全部标记为可到达。这个写法更稳但本质上还是把所有“可达区间”一个个画出来复杂度依然是 O(n²)。到这里很多人会觉得已经够好了。但面试官往往会追问一句“能不能再优化”2.3 贪心的转折点把“每步怎么跳”换成“最远能覆盖到哪”刚才的 DP 在空间和时间上浪费在一个地方它记住了每个位置是否可到达但实际问题关心的是整体覆盖范围。换个视角想只要能到达某个位置 i那么 0 到 i 之间的所有位置都已经在可达范围内了。因为在跳跃过程中你不可能跳过中间某个位置直接落到后面——你总得经过它们。于是我们不需要一个数组只需要一个边界变量来记录目前所有可到达位置里下标最大能到多少。这个变量通常叫maxReach最远可达位置。思路是这样一开始站在下标 0maxReach 0。顺序遍历数组对于每一个位置 i先检查一个致命条件如果 i 已经超过了maxReach说明中间出现了断点你根本走不到这里直接返回false。如果 i 在可达范围内就尝试用i nums[i]更新maxReach把它撑到更远。一旦maxReach超过或等于n - 1说明终点已经进入覆盖范围返回true。关键的一步是“尝试更新”而不是“模拟跳”。因为你并不需要知道具体怎么跳过去的只需要知道能不能把覆盖边界推过去。2.4 贪心为什么是对的我第一次接触这题时也怀疑过只维护一个最大边界会不会漏掉某些“必须小步跳才能到达终点”的特殊路线答案是不会。原因是这个覆盖边界一旦扩大就永久保留我们每一步都在取覆盖范围的最大值。哪怕当前位置的值是 0只要maxReach已经把它甩在身后数组遍历还能继续往后走。换句话说跳跃能力的“势能”被保存在maxReach里而不是绑定在某个具体位置上。用数学归纳法来看基础下标 0 总是可达所以maxReach至少包含 0。归纳如果遍历到位置 i 时 i 在可达范围内那么i nums[i]是可达的因此把maxReach更新为两者最大值后范围依然成立。结论整个遍历结束后所有被maxReach覆盖的位置都是可达的。终点一旦被覆盖问题答案就是true。所以贪心策略既不会漏解也不会误判。它牺牲了“具体路径”的细节换来了 O(n) 的遍历。3. 代码落地与复杂度分析3.1 Python 版核心代码直接上最常用的实现def canJump(nums): n len(nums) max_reach 0 for i in range(n): if i max_reach: return False max_reach max(max_reach, i nums[i]) if max_reach n - 1: return True return True这段代码只有五行核心逻辑但每一行的顺序都不能乱。第一if i max_reach必须在更新max_reach之前。一旦发现当前位置已经超出覆盖范围说明后面的位置更不可能到达可以直接结束。第二max_reach max(max_reach, i nums[i])用的是max不是直接赋值。因为某个更靠前的位置可能已经提供了更大的覆盖范围当前这个位置如果跳不远不应该把边界往回拉。第三if max_reach n - 1放循环内可以提前结束遍历。对于大数组这个提前返回能省不少时间。用示例一跟踪一遍[2, 3, 1, 1, 4]i 0max_reach max(0, 02) 2i 1max_reach max(2, 13) 4此时4 4返回true只遍历了两个位置就结束了。再看示例二[3, 2, 1, 0, 4]i 0max_reach 3i 1max_reach max(3, 12) 3i 2max_reach max(3, 21) 3i 33 3不成立所以进入更新max_reach max(3, 30) 3i 44 3成立返回false这里能看到一个关键细节即使下标 3 是 0因为max_reach还覆盖着它循环不会在第 3 轮直接退出。直到下一轮发现 i 已经超过边界才真正宣告失败。3.2 Java 版本和 C 版本实现很多工程岗面试要用 Java 或 C 手写顺手贴出一版 Javaclass Solution { public boolean canJump(int[] nums) { int n nums.length; int maxReach 0; for (int i 0; i n; i) { if (i maxReach) { return false; } maxReach Math.max(maxReach, i nums[i]); if (maxReach n - 1) { return true; } } return true; } }C 版本大同小异class Solution { public: bool canJump(vectorint nums) { int n nums.size(); int maxReach 0; for (int i 0; i n; i) { if (i maxReach) return false; maxReach max(maxReach, i nums[i]); if (maxReach n - 1) return true; } return true; } };三种语言的核心思路完全一样面试时你掌握任意一个版本都能顺畅地翻译成另一种语言。我建议平时练习时至少用两种语言各写一遍加深对代码结构的记忆。3.3 复杂度分析为什么只用 O(1) 额外空间时间复杂度是 O(n)因为整个数组最多被扫描一次循环体内的每个操作都是常数时间。空间复杂度是 O(1)因为除了一个max_reach变量没有任何随输入规模增长的存储结构。对比前面提到的 DFS 和 DP 版本这个优势在高约束下特别明显。LeetCode 原题的数据范围是数组长度最长可达一万O(n²) 的 DP 在最坏情况下要执行上亿次操作虽然数据量不大但已经能感受到性能差异。如果面试官把数组长度放大到几十万O(n²) 就会被立刻淘汰。提示面试时一定要自己主动说出“复杂度是 O(n) 时间、O(1) 空间”并且跟前面提到的暴力解做对比。这比只背代码得分高很多。4. 边界用例与实战踩坑记录4.1 面试时应该主动跑一遍的测试用例这题最容易翻车的地方不是主流程而是边界。下面这组用例是我建议你在刷题时逐一验证的输入结果说明[0]true起点就是终点不用跳[1]true同上长度为 1 直接成功[0, 1]false第一步就只能跳 0根本无法前进[1, 2, 3]true常规可达案例[2, 0, 0]true第一步直接跳 2 到终点[3, 2, 1, 0, 4]false经典 0 卡死点[1, 1, 1, 1, 1]true每步只跳 1稳步前进[5, 0, 0, 0, 0, 0]true一步就能从起点跳到终点特别提醒[2, 0, 0]这类例子。下标 1 和 2 都是 0但下标 0 的值是 2可以直接跳到终点。如果你用“模拟每一步怎么走”的思路很容易误判成失败但贪心只看覆盖范围第一轮就把max_reach更新到 2立刻返回 true。4.2 新手最容易犯的四个错误第一个错误把max_reach初始化成nums[0]然后从 i 1 开始遍历。对于长度大于 1 的数组这通常也没问题。但一旦数组只有一个元素且nums[0] 0这种初始化方式容易让代码习惯性地从 i 1 开始循环结果数组越界或返回错误。保险起见还是初始化成 0并且循环从 i 0 开始最稳妥。第二个错误在更新覆盖范围时写作max_reach i nums[i]而不是max_reach max(max_reach, i nums[i])。前者会丢失之前更靠前位置积累的跳跃势能。比如[2, 5, 0, 0]这种数组如果你在 i 1 时用1 5 6覆盖掉之前的 2那没问题但如果某个靠前位置跳得远、靠后位置跳得近不取 max 就会把边界往回缩直接导致误判。第三个错误先判断max_reach n - 1再更新。顺序反了会造成第一轮 i 0 时如果nums[0]恰好足够跳到终点逻辑上没问题但代码可读性变差某些复杂用例下容易漏判。正确的顺序是“先判断当前位置可达性再更新覆盖范围最后判断是否到终点”。第四个错误把“当前位置的值为 0”当成失败条件。[2, 0, 2, 0, 1]这种数组下标 1 是 0但你完全可以从下标 0 直接跳到下标 2。所以判断失败的唯一标准只有一条i max_reach。5. 由这题长出来的变体题型跳跃游戏家族5.1 LeetCode 45跳跃游戏 II从“能不能到”到“最少几步”这是最直接的一个变体。题目改为到达最后一个元素所需的最小跳跃次数是多少假设你总是可以到达最后一个位置。两题的关系类似于“判断可达”和“求最短路径”的关系。跳跃游戏 II 不再满足于一个max_reach你得同时知道“当前这一步能跳到的边界”和“下一步能跳到的最远边界”。经典做法是用 BFS 分层思想def jump(nums): n len(nums) jumps 0 cur_end 0 cur_farthest 0 for i in range(n - 1): cur_farthest max(cur_farthest, i nums[i]) if i cur_end: jumps 1 cur_end cur_farthest if cur_end n - 1: break return jumps这里的cur_end是当前这一跳覆盖的最远边界cur_farthest是边界内所有位置能继续延伸出的最远边界。每当遍历到达cur_end说明这一跳已经无法继续覆盖后面的位置必须把“下一跳覆盖边界”切换成cur_farthest同时跳跃次数加一。刷完跳跃游戏再刷这题你会明显感觉到难度梯度设计得特别好。5.2 LeetCode 1306跳跃游戏 III修改规则后变成 DFS/BFS另一道变体改变了“只能向右跳”的限制给定数组和一个起始下标每次你可以从 i 跳到i arr[i]或i - arr[i]问能否到达任意一个值为 0 的下标。这个变体是典型的图搜索问题因为目标不再是“最远覆盖”而是“指定目标可达”并且跳跃方向可变。常规解法是用队列做 BFS并记录访问过的下标防止死循环def canReach(arr, start): n len(arr) visited [False] * n queue [start] visited[start] True while queue: idx queue.pop(0) if arr[idx] 0: return True for nxt in (idx - arr[idx], idx arr[idx]): if 0 nxt n and not visited[nxt]: visited[nxt] True queue.append(nxt) return False两道题对比着看你会发现“贪心”和“BFS”各自适合什么场景印象会非常深。5.3 面试官可能怎么在跳跃游戏上改题面试官不会总满足于原题。常见改法有这么几类把“最大跳跃长度”改成“必须刚好跳这么远”。这时候贪心失效因为覆盖范围不再是单调扩展的每个位置能到达的点是确定的问题变成有向图上的可达性判断需要 BFS 或 DP。在跳跃过程中加入“能量消耗”每次跳跃消耗固定能量需要判断能量是否足够。这时候除了覆盖范围还要额外维护一个最大剩余能量本质也还是贪心但状态多了一维。把数组改成二叉树问你能否从根节点跳到某个叶子。树上的覆盖变成区间递归解法会变成树形 DP 或 DFS。碰到这种改题我的建议是先问清楚约束条件再回到暴力解找状态定义最后看有没有“单调覆盖”可以利用。很多时候面试官并不是真要你做出来而是看你能不能有条理地分析问题空间。6. 刷题心得与面试临场表达6.1 这道题给我留下的两个思维锚点第一遇到“能不能达到某个范围”的题先问自己一句问题能不能转化成覆盖区间问题跳跃游戏本质是“每个位置向右延伸出一个区间求这些区间的并集覆盖范围能到哪”。这个转化一旦完成解法基本就出来了。第二贪心不是不管正确性而是在每一步都选择一个“不会被更差选择超越”的最优决策。跳跃游戏的每个位置最多向右延伸如果当前位置跳得更远它覆盖的下一步选择只会更多不会更少所以“取最远”是安全的。我在实际刷题时发现这个“覆盖区间”的思维不光适用于跳跃题目很多类似“加油站”“合并区间”“安排会议”的贪心题底层都是同一个套路把操作转成区间再用一个变量维护边界。6.2 面试时怎么把这题讲得既快又稳如果你在面试中遇到这题建议按下面的顺序组织回答先确认题意和约束条件。比如“数组长度可以为 0 吗”“nums[i]的范围是多少”“我想确认一下你关心的是能否到达而非最少步数”。这一步能展示你的需求分析能力也能避免写错方向。接着抛出暴力思路和它的复杂度。不用真的写完整暴力代码口述一下“可以用 DFS 枚举每一步的落点最坏复杂度很高”就够了。然后话锋一转说“但因为所有位置只能向右延伸真正重要的只有当前可达范围的最远值”顺势给出贪心思路。写代码的时候边写边注释式地讲每一行的作用。先写max_reach 0再写 for 循环再写边界检查。代码写完主动用示例一跑一遍再顺口带一个边界用例[0]或者[0, 1]。最后报复杂度并补充一句“这段代码的时间是 O(n)空间是 O(1)”。如果面试官追问正确性就用“如果 i 在当前覆盖范围内它一定可达它能延伸到多远就决定覆盖范围能撑多远”来解释。多年刷题和带人准备面试的经验告诉我这题能不能把它讲得“跟散步一样轻松”往往能直接反映一个人对贪心的理解程度而不是记忆程度。6.3 一个提升手感的扩展练习如果你已经能闭眼写出标准解建议再做个压力测试随机生成超多数组每个数组长度几百到几千用暴力解和贪心解互相校验结果。多数人能想到贪心但很少有人真正观察过“贪心失败要满足什么条件”。在这题的约束下贪心不会失败你很快就能在随机用例中验证这一点。亲手跑一遍这种验证比你背十遍题解都有用。以后遇到判断“能不能连续覆盖”的新题你会下意识想起这个曾经亲手验证过的模型。我自己在刷完 LeetCode 55 之后又连续刷了跳跃游戏 II 和跳跃游戏 III明显感觉到三种题目的解法差异一个贪心一个 BFS 求最短路径一个是图搜索。三兄弟放在一起对照着做一遍比单独刷十道无关题目收获大得多。这也是我日常练习的一个小习惯同一家族的题目集中突破而不是东一榔头西一棒子。如果你最近也在刷这类题从这里开始然后再往变体延伸手感应该会提升得很快。