（LeetCodeHot100）55. 跳跃游戏——jump-game

55. 跳跃游戏——jump-game

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105
  • 这题说的是每次跳跃的最大长度是该下标的值
  • 我的第一想法是递归，从第一个元素开始，从最大开始跳，不行就跳的距离-1

我的错的离谱的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    boolean flag = false;
    public boolean canJump(int[] nums) {
        int index = 0; // 用于指明当前位置
        jump(index, nums);
        return flag;
    }

    private void jump(int index, int[] nums) {
        if (index == nums.length - 1) {
            return;
        }
        if (nums[index] < 0) {
            index++;
            jump(index, nums);
        }
        if (index + nums[index] >= nums.length - 1) {
            flag = true;
        }
        nums[index]--;
        jump(index, nums);
    }
}

改进一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public boolean canJump(int[] nums) {
        // 从下标 0 开始递归探索
        return backtrack(0, nums);
    }

    // 递归函数：探索从当前 index 能否到达终点
    private boolean backtrack(int index, int[] nums) {
        // 终止条件 1：当前位置就是终点 → 成功
        if (index == nums.length - 1) {
            return true;
        }
        // 终止条件 2：当前位置能跳的最大步数为 0 → 无法前进，失败
        if (nums[index] == 0) {
            return false;
        }
        // 终止条件 3：当前位置能直接跳到终点 → 成功
        if (index + nums[index] >= nums.length - 1) {
            return true;
        }

        // 尝试所有可能的跳跃步数（1 ~ nums[index]）
        for (int step = 1; step <= nums[index]; step++) {
            int nextIndex = index + step; // 跳跃后的下一个位置
            // 递归探索下一个位置，如果成功则直接返回（剪枝，不用再试其他步数）
            if (backtrack(nextIndex, nums)) {
                return true;
            }
        }

        // 所有步数都尝试过，无法到达终点 → 失败
        return false;
    }
}

还是超时：说明方法时间复杂度高了

官方解答

方法：贪心

我们可以用贪心的方法解决这个问题。

设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums[x]，这个值大于等于 y，即 x+nums[x]≥y，那么位置 y 也可以到达。

换句话说，对于每一个可以到达的位置 x，它使得 x+1,x+2,⋯,x+nums[x] 这些连续的位置都可以到达。

这样一来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新 最远可以到达的位置。

在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

以题目中的示例一

1
[2, 3, 1, 1, 4]

为例：

  • 我们一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；
  • 我们遍历到位置 1，由于 1≤2，因此位置 1 可达。我们用 1 加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此我们直接返回 True。

我们再来看看题目中的示例二

1
[3, 2, 1, 0, 4]
  • 我们一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；
  • 我们遍历到位置 1，由于 1≤3，因此位置 1 可达，加上它可以跳跃的最大长度 2 得到 3，没有超过最远可以到达的位置；
  • 位置 2、位置 3 同理，最远可以到达的位置不会被更新；
  • 我们遍历到位置 4，由于 4>3，因此位置 4 不可达，我们也就不考虑它可以跳跃的最大长度了。

在遍历完成之后，位置 4 仍然不可达，因此我们返回 False。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
  • 空间复杂度：O(1)，不需要额外的空间开销。

我的疑问

这个i <= max（rightmost）有什么用？

我问出这个问题说明还没有把关键把握：这题关键就是max是能到达的最远处，如果没有i <= max，i到了max+1话就错了，因为i到不了

详细解释：

这个判断 if (i <= max) 是 贪心算法的核心约束，目的是过滤掉「永远到达不了的位置」—— 只有当当前位置 i 是之前能到达的范围之内时，才需要用它更新 “最远可达距离”。如果少了这个判断，代码会出错（比如误把到达不了的位置算进去，导致逻辑失效）。

先明确两个关键概念

  1. max：表示「截至目前，能到达的最远下标」（初始为 0，因为一开始只能在第 0 位）；
  2. i：当前遍历到的下标（从 0 到 n-1）。

为什么必须加 if (i <= max)？

核心逻辑：只有当前位置 i 是 “可达的”，它才能为后续的跳跃做贡献。

举个反例（用你之前测试过的失败案例）：

nums = [3,2,1,0,4]（最终无法到达终点）

我们一步步模拟「不加 if (i <= max)」的情况，看看会出什么问题：

  • 初始：max=0，n=5（终点下标是 4）
  • i=0：i <= max（0<=0），更新 max = max(0, 0+3)=3 → 此时最远能到下标 3，没到终点，继续；
  • i=1：i <= max（1<=3），更新 max = max(3, 1+2)=3 → 最远还是 3；
  • i=2：i <= max（2<=3），更新 max = max(3, 2+1)=3 → 最远还是 3；
  • i=3：i <= max（3<=3），更新 max = max(3, 3+0)=3 → 最远还是 3（到这里卡住了，再也跳不动）；
  • i=4：如果没有 if (i <= max)，会执行 max = max(3, 4+4)=8 → 此时 max >=4，代码会错误返回 true（但实际 i=4 是终点，根本到不了！）。

看到了吗？如果不加这个判断，当 i=4 时（这个位置本身是 “不可达” 的），我们会错误地用它的 i + nums[i] 更新 max，导致代码误判为 “能到达终点”，但实际上 i=4 是我们永远到不了的位置，它的 nums[i] 没有任何意义。

再用正确逻辑模拟（加 if (i <= max)）

同样是 nums = [3,2,1,0,4]：

  • i=4 时，i=4 > max=3 → 不执行任何操作（跳过这个不可达的位置）；
  • 循环结束后返回 false，结果正确。

再看成功案例（验证逻辑合理性）

nums = [2,3,1,1,4]（能到达终点）：

  • 初始：max=0，n=5（终点下标 4）
  • i=0：0<=0 → max = max(0,0+2)=2；
  • i=1：1<=2 → max = max(2,1+3)=4 → max >=4，返回 true（正确）；
  • 后面的 i=2、3、4 都不用遍历了，提前终止。

总结：这个判断的作用

if (i <= max) 本质是「筛选有效位置」：

  • 只有 i 在 “之前能到达的范围” 内，这个位置的 nums[i] 才有可能拓展 “最远可达距离”；
  • 如果 i 超出了 max（即这个位置永远到不了），它的 nums[i] 再大也没用（比如 i=4 时的 nums[4]=4），因为我们根本到不了这个位置，自然无法用它跳跃。