跳跃游戏 图解题解

这道题到底在问什么

nums

[2, 3, 1, 1, 4]

输出

true

先想最直接的笨办法

在每一格都枚举「跳 1 步、跳 2 步…」一路递归试到底，路径会指数爆炸，还会反复算同一格能不能到终点。其实根本不必关心怎么跳。（动画第 3 步）

最优解：一步一步想明白

1. 3在每一格都枚举「跳 1 步、跳 2 步…」一路递归试到底，路径会指数爆炸，还会反复算同一格能不能到终点。其实根本不必关心怎么跳。
2. 4转折：从左往右扫，只要一个格子在 maxReach 范围内能站住，它能到的地方我就也能到。所以每到一格就用 maxReach = max(maxReach, i + nums[i]) 把边界往外推。一旦 maxReach 盖过终点就成；要是走到某格时 i 已经超出 maxReach，说明这格根本站不上去，卡死返回 false。贪心成立的关键：能到的范围是连续的一段，维护它的右边界就行。
3. 5maxReach = 2站在 0 号位能跳 2 步，最远摸到 2 号位。橙色区间就是当前你够得着的范围 [0, 2]。
4. 6maxReach = 41 号位在可达范围内（1 ≤ 2），站得上去。它能跳 3 步到 4 号位，maxReach 被推到 4——已经盖住终点了，但我们把扫描走完看看每步怎么动。
5. 7maxReach 仍 = 42 号位也在范围内。它只能跳 1 步到 3 号位，比现有的 4 近，maxReach 不更新，仍是 4。
6. 8maxReach 仍 = 43 号位还在范围内，它能到的 4 号位也没超过现有边界。maxReach 保持 4。
7. 9maxReach 4 ≥ 终点 4走到最后一格 4，它本身就在可达范围内（4 ≤ maxReach=4）。能到达，返回 true。
8. 10maxReach = 3换个会失败的数组 [3,2,1,0,4]。0 号位跳 3 步，maxReach=3，范围 [0,3]——终点 4 还差一格够不到。
9. 11maxReach 仍 = 31 号位在范围内，它能到 1+2=3，没超过现有边界，maxReach 不动，还是 3。范围卡在 [0,3] 里推不出去。
10. 120 号挡路 → maxReach 停 3一路走到 3 号位，它的值是 0，3+0 还是 3，maxReach 推不动了。下一步 i=4 时 4 ＞ maxReach=3，站不上去 → 返回 false。一个 0 卡在关键位置就能堵死整条路。
11. 15不纠结具体怎么跳、跳几次，只维护全局的「可达右边界」maxReach，让它一路向外推——这就是可达性贪心。
12. 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def canJump(self, nums):
        maxReach = 0
        for i, jump in enumerate(nums):
            if i > maxReach:
                return False
            maxReach = max(maxReach, i + jump)
        return True

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            if (i > maxReach) return false;
            maxReach = max(maxReach, i + nums[i]);
        }
        return true;
    }
};

class Solution {
    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]);
        }
        return true;
    }
}

# 可达边界贪心 骨架
maxReach = 0
for i, x in enumerate(nums):
    if i > maxReach:          # 当前下标已超出能到的最远 → 卡死
        return False
    maxReach = max(maxReach, i + x)
    if maxReach >= len(nums) - 1:   # 已能盖住终点，提前结束
        return True
return True

复杂度

面试官可能追问