55. 跳跃游戏

题目链接（中等）

题目描述

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

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

数据范围：

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

示例

示例 1：

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

示例 2：

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

方法一：贪心（维护最远可达位置）

思路及解法

用贪心的视角看这个问题：对于每一个可以到达的位置 x，它能覆盖 x+1, x+2, ..., x+nums[x] 这些连续位置。因此，只要从左到右遍历数组，实时维护当前能到达的最远下标 rightmost：

• 若当前位置 i <= rightmost，说明 i 可达，用它更新 rightmost = max(rightmost, i + nums[i])；
• 若 rightmost >= n - 1，说明最后一个位置已经可达，直接返回 True；
• 若某次 i > rightmost，说明当前位置已经无法到达，后面的位置更不可能到达，遍历结束返回 False。

直觉理解：不需要关心具体怎么跳，只要知道“能到达的最远位置”一直在扩展就够了。如果最远位置能覆盖到终点，就一定能到。

代码

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        n = len(nums)
        reach = 0
        for i in range(n):
            if i > reach:
                return False
            reach = max(reach, i + nums[i])
            if reach >= n - 1:
                return True
        return False

也可以把 i > rightmost 的判断提前成 if i <= rightmost: 包住循环体，逻辑相同。

复杂度分析

• 时间复杂度：$O(n)$，只需遍历数组一次。
• 空间复杂度：$O(1)$，只使用常数个变量。