跳跃游戏 图解题解

跳跃游戏这道题在问什么

从下标 0 出发，nums[i] 表示站在 i 处最多能往前跳的步数——注意是「最多」，跳 1 步到 nums[i] 步之间随便选。问能否到达最后一个下标，答案只要 true 或 false。这是个存在性问题：不问最少跳几次，也不用给出跳法，只判定「有没有一条路」。抓住这一点，就不必执着于还原具体路线。

为什么不能枚举每一种跳法

直觉做法是搜索：站在每个位置，把 1 到 nums[i] 步的每种跳法都递归试一遍。可行是可行，但路线数量随数组长度指数增长，必然超时；即便加记忆化做成 DP，也要 O(n²) 级别的转移。反过来想，题目只要一个布尔答案，为每条具体路线付出代价本身就是浪费——存在性问题往往有比「逐一枚举方案」粗得多的判据，这道题的判据就藏在可达位置的形状里。

为什么一个 maxReach 变量就够了

关键观察：能到达的下标集合，一定是从 0 开始的一段连续前缀，中间不会有洞。理由很简单——nums[i] 是「最多」跳的步数，能从某个可达位置跳到 j，就能从同一个位置少跳几步落在 j 之前的任何格子上，所以「能到 j」蕴含「j 左边全都能到」。

既然可达集是一段连续区间 [0, maxReach]，描述它只需要右端点这一个数。整道题于是被压缩成：从左到右扫，看这条边界能被推到多远、中途有没有断——这就是贪心算法只维护一个 maxReach 的底气，不用记任何具体跳法。

扫描中每一步的判定为什么成立

扫到下标 i 时先检查：若 i <= maxReach，说明 i 落在可达前缀里，i 本身可达，那么从 i 起跳能覆盖到 i + nums[i]，用它刷新 maxReach，即 maxReach = max(maxReach, i + nums[i])；一旦 maxReach >= n - 1，终点已进入可达范围，提前返回 true。若 i > maxReach，说明前面所有位置合力也够不到 i，而 i 右边的格子只会更远，边界永远断在这里，返回 false。

示例 [3,2,1,0,4] 正是断链的典型：前四个位置把边界最多推到 3，下标 4 够不着，false。它同时说明「遇到 0 就完蛋」是误判——0 本身不产生推进，但只要之前的边界已经越过它（比如 [2,3,1,1,4] 也含跳 1 步的格子照样能通），0 就只是路过的一格。真正的死因从来不是某个 0，而是边界恰好停在 0 上再也推不动。

复杂度多少，哪些细节容易写错

数组从左到右扫一遍，每个下标只做常数次比较和取 max，时间 O(n)；除 maxReach 外不开任何额外结构，空间 O(1)。

最容易写错的是断链判定的边界：条件是 i > maxReach 才 false，写成 i >= maxReach 会把「恰好踩在边界上」的可达位置误判成够不着。另一个理解性的坑上一节已拆过：0 不必特判。延伸一问：如果要求最少跳几次到终点，那是跳跃游戏 II（LeetCode 45），贪心升级成分层推进边界，依然 O(n)。

Python

def canJump(nums):
    max_reach = 0                  # 目前能到达的最远下标
    for i in range(len(nums)):
        if i > max_reach:          # 连 i 都到不了
            return False           # 边界断了，跳不过去
        max_reach = max(max_reach, i + nums[i])  # 刷新最远
        if max_reach >= len(nums) - 1:
            return True            # 已能够到末尾
    return True

C++

bool canJump(vector<int>& nums) {
    int maxReach = 0;                 // 能到达的最远下标
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        if (i > maxReach) return false;   // 到不了 i，断了
        maxReach = max(maxReach, i + nums[i]);  // 刷新最远
        if (maxReach >= n - 1) return true;     // 够到末尾
    }
    return true;
}

Java

public boolean canJump(int[] nums) {
    int maxReach = 0;                 // 能到达的最远下标
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        if (i > maxReach) return false;   // 到不了 i，断了
        maxReach = Math.max(maxReach, i + nums[i]);  // 刷新最远
        if (maxReach >= n - 1) return true;          // 够到末尾
    }
    return true;
}