这道题是 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（最远可达位置）。思路是这样：
- 一开始站在下标 0，
maxReach = 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 = 0：
max_reach = max(0, 0+2) = 2 - i = 1：
max_reach = max(2, 1+3) = 4，此时4 >= 4，返回true
只遍历了两个位置就结束了。
再看示例二[3, 2, 1, 0, 4]：
- i = 0：
max_reach = 3 - i = 1：
max_reach = max(3, 1+2) = 3 - i = 2：
max_reach = max(3, 2+1) = 3 - i = 3：
3 > 3不成立，所以进入更新，max_reach = max(3, 3+0) = 3 - i = 4：
4 > 3成立，返回false
这里能看到一个关键细节：即使下标 3 是 0，因为max_reach还覆盖着它，循环不会在第 3 轮直接退出。直到下一轮发现 i 已经超过边界，才真正宣告失败。
3.2 Java 版本和 C++ 版本实现
很多工程岗面试要用 Java 或 C++ 手写，顺手贴出一版 Java：
class 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(vector<int>& 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 求最短路径，一个是图搜索。三兄弟放在一起对照着做一遍，比单独刷十道无关题目收获大得多。这也是我日常练习的一个小习惯：同一家族的题目，集中突破，而不是东一榔头西一棒子。如果你最近也在刷这类题，从这里开始，然后再往变体延伸，手感应该会提升得很快。
