55. 跳跃游戏

题目链接：55. 跳跃游戏

题目描述

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

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

核心思考：贪心算法（维护最远覆盖范围）

判断是否能到达终点，本质上是看我们在行进过程中，能够触及到的最远边界是否能覆盖到终点。这是一个典型的贪心（Greedy）问题。

1. 状态变量：维护一个变量 max_，代表当前所有已访问跳板中，能够跳到的最远下标位置。
2. 遍历与决策：
   • 依次遍历数组中的每个位置及其跳跃能力。
   • 可达性检查：如果当前下标 index 已经超过了目前所能触及的最远范围 max_，说明我们永远无法走到当前这个格子，自然也就无法到达终点，直接返回 False。
   • 动态更新：如果当前格子可达，我们就尝试更新最远边界：max_ = max(max_, index + jump)。
3. 提早结束：如果在某一步更新后，max_ 已经大于或等于数组的最后一个下标 len(nums) - 1，说明大局已定，可以直接判定为 True。

通过这种“只管最远能到哪”的贪心策略，我们能以线性的代价给出最终答案。

解题思路 (Python)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_ = 0
        for index, jump in enumerate(nums):
            # 如果当前位置已经超出了目前能跳到的最远范围
            if index > max_:
                return False
            
            # 更新当前能跳到的最远覆盖范围
            max_ = max(max_, index + jump)
            
            # 如果最远范围已经覆盖了终点
            if max_ >= len(nums) - 1:
                return True
        
        # 兜底返回（实际上在循环中通常能出结果）
        return max_ >= len(nums) - 1

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。我们只需要对数组进行一次线性扫描。
• 空间复杂度：$O(1)$。我们只使用了一个额外的变量来存储当前的最远距离。
  说明：为了逻辑严谨性，最后添加了对 max_ 的兜底判断，确保逻辑链条的完整。