京公网安备11010502063487号给定一个非负整数数组，你站在下标 0，每个元素表示从这个位置最多能向前跳的步数，问能否到达最后一个位置。动态规划是 O(n²)：逐个位置推出能到的所有位置。贪心是 O(n)：从左到右扫描，只维护"目前能到达的最远位置" farthest；如果扫描到的位置 i 已经超过 farthest，说明连这个位置都到不了，直接返回失败；每个能到达的位置都更新 farthest，一旦它够到（或超过）最后一个位置，就成功了。本文用真实数据展示漏掉"到不了"检查的后果，实测贪心和递推的耗时，给出五种语言的实现，并把扫描过程做成分步演示。
完整题目见官方页面（链接在文末）。基准解是逐个位置向前推：reach[i] 为真时，把它能到的位置都标为真，是 O(n · 步数) 的另一种思路。一共 14 组用例，覆盖：官方两个示例、只有一个元素、卡在 0 上、一步就能越过 0 的情形：
输入 [[2,3,1,1,4]] 输出 true 输入 [[3,2,1,0,4]] 输出 false 输入 [[0]] 输出 true 输入 [[0,1]] 输出 false 输入 [[1,0]] 输出 true 输入 [[2,0,0]] 输出 true
如果只是把所有位置的 i + nums[i] 取最大值，最后比较是否够到终点，就忽略了"某个位置根本到不了"这一点：例如 [3, 2, 1, 0, 4]，从下标 0 能到下标 3，但下标 3 的值是 0，走不出去；下标 4 的值 4 让最大值变成 8，看起来能到终点，可是下标 4 本身就到不了。下面是这种写法与 solve 的真实结果：
# 没有「位置 i 已经到不了」检查的写法 [3, 2, 1, 0, 4]: 只看最终 farthest -> True solve -> False [0, 5]: 只看最终 farthest -> True solve -> False [1, 0, 5]: 只看最终 farthest -> True solve -> False [2, 3, 1, 1, 4]: 只看最终 farthest -> True solve -> True 随机 20000 个数组：这种写法与正确答案不同的有 12221 个（61.1%）
[3, 2, 1, 0, 4]、[0, 5]、[1, 0, 5] 三组都被错误地判为 True，正确答案是 False。在我用的随机数据里（取值偏向 0，让"到不了"的情形占很大比例），这种写法与正确答案不同的有 12221 组，占 61.1%；这个比例取决于数据里 0 的多少，不同分布下会不同。正确的写法是在扫描每个位置时先检查 i > farthest。
farthest 从 0 开始。对每个位置 i：如果 i > farthest，返回 False；否则 farthest = max(farthest, i + nums[i])；如果 farthest >= n - 1，返回 True。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): farthest = 0 # 目前能到达的最远位置 for i, step in enumerate(nums): if i > farthest: # 连位置 i 都到不了，后面更到不了 return False farthest = max(farthest, i + step) if farthest >= len(nums) - 1: # 已经能到达（或越过）最后一个位置 return True return True
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,3,1,1,4]] → true [[3,2,1,0,4]] → false [[0]] → true [[0,1]] → false [[1,0]] → true [[2,0,0]] → true
Java · 解法代码class Solution { public boolean canJump(int[] nums) { int farthest = 0; // 目前能到达的最远位置 for (int i = 0; i < nums.length; i++) { if (i > farthest) return false; // 连位置 i 都到不了，后面更到不了 farthest = Math.max(farthest, i + nums[i]); if (farthest >= nums.length - 1) return true; // 已经能到达（或越过）最后一个位置 } return true; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,3,1,1,4]] → true [[3,2,1,0,4]] → false [[0]] → true [[0,1]] → false [[1,0]] → true [[2,0,0]] → true
Go · 解法代码func canJump(nums []int) bool { farthest := 0 // 目前能到达的最远位置 for i, step := range nums { if i > farthest { // 连位置 i 都到不了，后面更到不了 return false } if i+step > farthest { farthest = i + step } if farthest >= len(nums)-1 { // 已经能到达（或越过）最后一个位置 return true } } return true }
$ go build -o bin . && ./bin < cases.jsonl [[2,3,1,1,4]] → true [[3,2,1,0,4]] → false [[0]] → true [[0,1]] → false [[1,0]] → true [[2,0,0]] → true
JavaScript · 解法代码function canJump(nums) { let farthest = 0; // 目前能到达的最远位置 for (let i = 0; i < nums.length; i++) { if (i > farthest) return false; // 连位置 i 都到不了，后面更到不了 farthest = Math.max(farthest, i + nums[i]); if (farthest >= nums.length - 1) return true; // 已经能到达（或越过）最后一个位置 } return true; }
$ node run.js < cases.jsonl [[2,3,1,1,4]] → true [[3,2,1,0,4]] → false [[0]] → true [[0,1]] → false [[1,0]] → true [[2,0,0]] → true
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: bool canJump(vector<int>& nums) { int farthest = 0; // 目前能到达的最远位置 for (int i = 0; i < (int)nums.size(); i++) { if (i > farthest) return false; // 连位置 i 都到不了，后面更到不了 farthest = max(farthest, i + nums[i]); if (farthest >= (int)nums.size() - 1) return true; // 已经能到达（或越过）最后一个位置 } return true; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[2,3,1,1,4]] → true [[3,2,1,0,4]] → false [[0]] → true [[0,1]] → false [[1,0]] → true [[2,0,0]] → true
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
数组长度分别为 1000、3000、1 万、100 万，每个元素是 1 到 3 的伪随机数（保证能到达终点），每个规模取三次中最快的一次：
数组长度 n（每个元素 1 到 3，能到达） | 暴力解 | 本文解法
1000 | 0.130 ms | 0.068 ms
3000 | 0.374 ms | 0.211 ms
10000 | 1.283 ms | 0.723 ms
1000000 | （未测，太慢） | 75.142 ms贪心与递推两种做法在这批数据上都是线性增长（1000 到 1 万，贪心 0.068ms 到 0.723ms，约 10.6 倍），并且差距不大：因为每个元素的步数很小（1 到 3），递推的内层循环很短，退化不成平方，贪心的优势没有体现出来。如果步数很大，递推的内层循环会变长，那时才能看出差距，这里没有实测。100 万个元素时贪心用了 75.1ms。
Python 版本另外和递推做了随机对拍，数组长度 1 到 12，取值偏向 0/1/2/3，能到达和到不了的各占一部分：
随机对拍 20000 组（长度 1 到 12、取值偏向 0/1/2/3 的随机数组（0 出现得很多，这样「到不了」的情形也占一半左右）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方的第二个示例 [3, 2, 1, 0, 4]。i = 0 时 farthest 变成 3，之后每个位置最远都只能到 3（i + nums[i] 都是 3），farthest 停在 3；扫描到 i = 4 时，它已经超过 farthest = 3，位置 4 到不了，返回 False。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。