企业官网建设流程全解析

1. 题目拆解：它到底在考什么

LeetCode 55题“跳跃游戏”我当年第一次刷到的时候，觉得这题不就是模拟一下跳格子吗？结果真动手才发现，模拟路径会把你绕进死胡同——因为你永远不知道在某一个位置应该选哪条跳法才是最优的。后来看题解知道了贪心算法这个思路，再回头来看这题，真的就是一层窗户纸的事。

这道题本质上是个“可达性判断”问题：给你一个非负整数数组nums，你从下标0出发，每个元素nums[i]表示你在下标i位置最多可以往后跳的步数，问你能不能跳到最后一个下标。注意“最多”这两个字，它意味着你在任意位置可以选择跳0到nums[i]之间的任意步数，不需要恰好用完。

这题在Hot 100里的定位很明确：贪心算法的入门经典。但它的难度标的是中等，因为贪心思路虽然好理解，可如果你没接触过，很容易往DFS、BFS、动态规划这三个方向跑，然后发现要么超时、要么写复杂了。

我帮你把题目里真正隐含的考点列一下：

• 你不需要输出具体跳法，只需要判断“是否可达”，这就暗示了最优解不需要记录路径。
• 每个位置能跳的步数是一个“上界”，不是绳子的长度，不是一定要拉满，这给贪心留了余地。
• 数组长度可能很大（题目限制1 <= nums.length <= 10^4，真实面试里可能更大），所以时间复杂度至少要控制在O(n)级别，O(n^2)的DP解法在极端情况下会触限。

所以这题适合谁来刷？我的建议是：准备面试的、刚开始刷LeetCode想建立贪心感觉的、以及做算法复盘想提高“题目归类”能力的同学。它不复杂，但作为思维训练价值很高——你能通过这一题掌握一类“维护可达区间并不断扩张”的问题模型。

2. 核心思路推导：为什么贪心是对的

我先带你走一遍“如果不用贪心会怎样”的心路历程，你就知道贪心这个方案为什么是顺理成章的了。

2.1 模拟路径的死胡同

新手最容易想到的做法是DFS：从位置0开始，枚举跳1步、2步……直到nums[0]步，每个分支继续递归下去，只要有一个分支到达末尾，就返回true。

这个思路没有错，但问题是分支爆炸。假设nums = [3, 3, 3, ...]，每一层都有3个选择，深度是n层，时间复杂度是O(3^n)级别。就算你加记忆化，把“已经访问过的下标”标记掉，时间复杂度依然可以到O(n^2)甚至更糟，因为一个位置可能被不同路径重复访问多次。

另外一个更隐蔽的坑是：模拟路径时你会下意识觉得“跳得越远越好”，但出题人专门设计了反例来打脸这个直觉。比如nums = [3, 2, 1, 0, 4]，你从0开始直接跳到3，结果下标3是0，卡死了；反而先跳到1，再跳到4才能成功。这说明“下一步最优”不等于“全局最优”，而这类“局部最优能推导全局最优”的场景，恰好就是贪心算法解题的信号。

2.2 反向思考：从“跳多远”变成“能覆盖多远”

既然不需要具体路径，我们不妨换个视角：每到一个位置，我们并不关心“具体怎么跳”，只关心“当前能到达的最远下标是多少”。

把数组想象成一条跑道，每个位置告诉你“你最多能从这里再飞多远”。那么从起点开始，每往前走一步，你手里那张“最远范围地图”就会更新一次——如果当前位置能到达，并且从它出发能跳得更远，就把最远可达边界扩大；如果遍历到某个位置时，它已经超出了当前最远边界，说明前面就是断头路，怎么都过不去。

这个“最远可达边界”（通常记为maxReach）就是整个贪心策略的灵魂。维护它只需要一次遍历，每个位置只处理一次，时间复杂度O(n)，空间复杂度O(1)。

我用大白话再翻译一遍：你每到一个加油站，都看一眼“从这里加满油能开到哪”，然后把你手里那张地图上能覆盖的范围往外扩一圈。只要地图的最远边界永远大于等于你当前所在的位置，你就永远有油可开；哪天边界追不上你了，游戏结束。

2.3 两种等价实现视角

这里有个小细节值得玩味：贪心可以有两种遍历方向，一种是我上面说的正向维护maxReach，另一种是反向从终点往前推。我先把正向的伪代码逻辑写出来给你感受一下：

def can_jump(nums): max_reach = 0 # 当前能到达的最远下标 for i in range(len(nums)): if i > max_reach: # 当前位置已经够不到了 return False max_reach = max(max_reach, i + nums[i]) return True

反向思路则像“从终点倒着找谁能到它”：维护一个变量lastPos，表示当前需要被到达的位置，从倒数第二个位置往前扫，如果某个位置加上它的跳跃力能覆盖到lastPos，就说明这个位置可以作为新的“跳板起跳点”，把lastPos往前挪到它。最终只要lastPos能挪到0，就说明可以从0一路跳到终点。

两种写法都能AC，但正向maxReach写法更直观、更不容易写错，我后面重点讲它。反向写法留给读者自己思考，其实它更能帮你看清楚这个数组里哪些位置是“关键跳板”。

3. 代码实现与逐行解读

3.1 正向贪心完整实现

我平时刷题主力语言是Java和Python，这里两个版本都给你。先看Java版本，这也是面试中最常见的语言：

public boolean canJump(int[] nums) { int maxReach = 0; for (int i = 0; i < nums.length; i++) { if (i > maxReach) { return false; // 当前位置不可达 } maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= nums.length - 1) { return true; // 提前结束，能到终点 } } return true; }

Python版本更简洁，几乎没有语法噪音：

class Solution: def canJump(self, nums: List[int]) -> bool: max_reach = 0 n = len(nums) 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

我推荐你在代码里保留“提前返回”这个优化。虽然不写它也AC，但实测在数组很大的场景下，提前结束能省掉不少无意义的遍历。比如nums = [0, 0, 0, ..., 0]且第一个位置就是0，循环跑一轮就结束了，但如果你把maxReach >= n-1的检查放在循环末尾，性能差异不会很明显；真正提速的场景是像nums = [100, 0, 0, ..., 0]这种，第一步就能直接覆盖终点，完全不用继续扫。在LeetCode的测试数据里，加不加提前返回都是0ms和1ms的区别，但面试时你把这一点讲出来，面试官会觉得你注意到了边界性优化。

3.2 为什么循环结束还要return true

有个细节我见过很多同学问：如果循环正常走完了，到底该返回什么？仔细想一下，循环正常结束意味着i从0一路走到了n-1，并且每次i <= maxReach都成立。既然最后一个位置都被走到了，那必然是可达的，所以返回true没错。

但如果循环中某个位置出现了i > maxReach，说明在前面的所有可选跳跃中，没有任何一种方案能让你到达现在这个位置，数组在这里出现了“断层”，此时立刻return false返回即可。

这两条路径覆盖了所有情况，不存在第三种“循环结束但不确定”的状态，所以你不需要在循环后再额外判断什么。

3.3 一个别出心裁的等价写法：区间合并思路

我还见过一种写法，它把maxReach理解成一个“不断扩张的区间”。初始区间是[0, 0]，因为下标0一定可达。每次遍历区间内的位置，就用max(i + nums[i])来尝试把区间的右端点向右推，直到左端点超过右端点，说明区间扩张不动了。

def can_jump(nums): left = right = 0 # 当前可达区间的左右边界 n = len(nums) while left <= right and right < n - 1: nxt = right for i in range(left, right + 1): nxt = max(nxt, i + nums[i]) left = right + 1 right = nxt return right >= n - 1

这种写法更像是BFS的层序遍历视角：每一层就是当前可达范围，下一层的右边界由这一层所有位置共同决定。虽然它的平均复杂度和贪心一样能过，但写起来繁琐，不推荐作为面试的答案。这里放出来只是为了让你看到同一个模型可以有多种表达形式，真正理解maxReach的本质后，你怎么写都不会错。

4. 复杂度分析与边界条件测试

4.1 时间与空间复杂度

正向贪心版本：

• 时间复杂度：O(n)，每个元素最多访问一次。
• 空间复杂度：O(1)，只用一个maxReach变量。

负向版本同样是O(n)时间、O(1)空间，只是常数项略有不同。这里我多提一句：如果你一开始用DP做这题，状态转移是dp[i] = OR(dp[j] && j + nums[j] >= i)，需要两层循环，时间复杂度O(n^2)，空间复杂度O(n)。虽然也能过（因为n <= 10^4时O(n^2)约1亿次，勉强能压线），但面试时用DP解这道题，面试官往往会追问一句“能不能优化”。这时候你把贪心方案亮出来，就是标准答案。

4.2 边界条件盘点

我总结了这题会出现的几类边界场景，写了个小测试表，你刷题时可以用来自检：

特别说下[3, 2, 1, 0, 4]这个用例：它最远能跳到3，但下标3的值是0，属于“看似能跳很远实则断头”的场景。这种反例就是用来敲打那些“只模拟最远路径”的新手思维的。你要是能把这个用例的分析讲给面试官听，会显得你思考过反例。

4.3 一个容易想当然的隐藏坑

有些同学看完maxReach = max(maxReach, i + nums[i])之后会问：“既然直接维护最远边界就行，那我在每个位置都贪心地取最大跳跃数，不就是最优解了吗？”

这里必须区分两个概念：维护最远可达边界和每一步都跳最远是两码事。前者的含义是“在所有可达位置中取能扩展的极限”，它是一个集合的并集思想；后者是“动规里那种只看眼前一步的决定”，后者才是真正的贪心陷阱。本题的贪心本质是“用可达位置集合作决策”，而不是“用跳跃策略作决策”，想明白这一点，你就不会被[3, 2, 1, 0, 4]这种用例绕进去了。

5. 常见问题与现场排查方式

刷题和笔试最烦的就是“代码看着没问题但就是WA”。我把这题常见的翻车方式整理了一下，并附上定位方法。

5.1 问题一：忘记了i > maxReach的判断

这个是最常见的错误。如果不加这个判断，循环会一直跑下去，任何情况最后都会返回true。比如[1, 0, 1]，不加判断时，i=1时maxReach还是1，虽然能处理；但[0, 1]这个用例下，i=0时 maxReach 更新为0，到i=1时如果没检查，就会继续执行max(maxReach, 1+1)算出2，最后误判为true。

排查技巧：写完后自己手动跑[0, 1]和[0, 2, 3]这两个极端用例，一步就能暴露问题。

5.2 问题二：提前返回条件写成了maxReach >= n

终点下标是n-1，不是n。写成>= n意味着你必须越界才算赢，这会导致[2, 0, 0]这种“恰好停在终点”的正确场景被判为false。虽然很多题解里写成>= n-1和> n-2都行，但>= n是错的，这一点我见过不止一个人踩过。

5.3 问题三：试图用DFS记忆化，结果超时

这个不算bug，算是思路问题。如果你写DFS版，可以过一部分数据，但n=10^4的极端数据会TLE。你可以记住：这道题的判断性质太强了，它只要求“能不能到”，没有要求“最少几步到”，也没有要求“有几种到法”。以后看到“只判断可行性”的题目，优先往贪心、双指针方向想，DFS和DP往往是万不得已的保底思路。

5.4 问题四：动态规划写出来了但状态转移写错

如果你确实想练DP，状态定义应该写成dp[i]表示“从起点能否到达i”。转移时要遍历所有j < i，满足dp[j] == true && j + nums[j] >= i即可。注意这不是求“最小步数”，别不小心把状态定义写成步数。这题用DP做是杀鸡用牛刀，但作为练习理解两种思路的差异，价值还是有的。

我个人的排查习惯是：把样例扩成“最长为1、最长能跳0、起点即终点”这三类极值用例，先手算过再交。刷到后面你会发现，80%的WA都能靠极端用例在30秒内定位出来。

6. 从这题延伸出去的同类模型

跳跃游戏这个模型在Hot 100里不是孤立的，它和好几道题共用同一个思维内核，我顺手帮你串一下，刷题效率会高很多。

6.1 45题“跳跃游戏II”——让贪心更完整的一道

那道题要求你用最少步数跳到终点。思路从“维护一个最远边界”升级成“维护当前步的可达边界和下一步的可达边界，步数在跨越边界时加1”。本质上还是贪心，但多了层“按步分层”的思维。如果你先吃透55题，45题就是加了个计数器的变体。

反过来想，55题还有一个变体叫“跳跃游戏III”，改成BFS从某个起点出发，问能不能到达值为0的位置，那就是另一类图遍历问题了，和本题的贪心模型思路不同，不要混在一起。

6.2 与“加油站”类问题的共性

LeetCode 134题“加油站”有个非常像的思维：从某个起点出发，维护一个累计油量，如果中途油量变负，就换起点。它的思想里也有“可达性”和“余量”的痕迹。区别在于55题没有环、没有资源消耗，更简单。做134题之前先做55题，会让你对“维护一个可行范围/累计量”这个模式更有手感。

6.3 面试中怎么讲这题才加分

我在模拟面试中总结了一套讲法，你可以参考：

• 第一步：快速确认题意，“这题是判断型问题，只要布尔结果，不要路径”。
• 第二步：讲反例，说明模拟具体跳法不可行。
• 第三步：讲核心变量maxReach的含义。
• 第四步：说边界条件：i > maxReach时直接false。
• 第五步：提优化提前返回，然后分析复杂度。

这五步下来，面试官基本就给你点头了。如果他还想深挖，通常会问“如果改成最少步数怎么办”，这时候你把45题的口头思路讲一下，就是加分项。我自己面过几家大厂，这道题被问到的概率不算低，但多数是作为贪心第一题试水，答得干净利落非常加分。

这题我刷了不下十遍，每次有不同的体会。最开始背答案，后来理解maxReach，再后来能从“1D可达区间扩张”的角度去迁移到其他题，这个过程本身比AC一道题有价值得多。如果你正在按Hot 100顺序刷，走到55题这里，值得慢下来把这个模型想通透——它属于那种花一小时想明白、后面能省十小时的题目。