实战：跳跃游戏 ​

LeetCode 55. 跳跃游戏 | 难度：中等

判断可达性的贪心经典，理解"最远可达"思想的最佳入口。

📎 LeetCode 55. 跳跃游戏

题目描述 ​

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

判断是否能到达最后一个位置。

示例：

输入：nums = [2,3,1,1,4]
输出：true
解释：从位置0跳1步到位置1，再跳3步到最后

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样都会到达位置3，该位置最大跳跃长度为0，无法继续

思路分析 ​

问题本质 ​

这道题问的不是"最少跳几次"，而是"能不能到达"。这意味着我们不需要追踪具体路径，只需要判断可达性。

关键洞察 ​

想象你站在位置 i，能跳 nums[i] 步。那么你可以到达 i+1, i+2, ..., i+nums[i] 中的任意位置。

核心问题：从起点开始，能到达的最远位置是多少？

贪心策略 ​

维护一个变量 maxReach，表示当前能到达的最远位置。

遍历每个位置：

1. 如果当前位置 > maxReach，说明无法到达当前位置，返回 false
2. 否则，更新 maxReach = max(maxReach, i + nums[i])
3. 如果 maxReach >= n-1，已经能到达终点，返回 true

代码实现 ​

function canJump(nums: number[]): boolean {
  let maxReach = 0;  // 当前能到达的最远位置
  
  for (let i = 0; i < nums.length; i++) {
    // 关键判断：当前位置是否可达
    if (i > maxReach) {
      return false;  // 无法到达位置 i，游戏失败
    }
    
    // 更新最远可达位置
    maxReach = Math.max(maxReach, i + nums[i]);
    
    // 优化：已经能到达终点，提前返回
    if (maxReach >= nums.length - 1) {
      return true;
    }
  }
  
  return true;
}

代码逻辑详解 ​

为什么 i > maxReach 就一定失败？

maxReach 是从位置 0 到 i-1 所有位置能跳到的最远距离的"并集"。如果这个并集都到不了位置 i，说明 i 完全不可达。

执行过程详解 ​

示例1：能到达 ​

nums = [2, 3, 1, 1, 4]
目标：到达位置 4

i=0: 
  0 <= maxReach(0) ✓ 可以访问位置0
  maxReach = max(0, 0+2) = 2

i=1: 
  1 <= maxReach(2) ✓ 可以访问位置1
  maxReach = max(2, 1+3) = 4 >= 4
  → 已经能到终点，返回 true

示例2：无法到达 ​

nums = [3, 2, 1, 0, 4]
目标：到达位置 4

i=0: 
  0 <= maxReach(0) ✓
  maxReach = max(0, 0+3) = 3

i=1: 
  1 <= maxReach(3) ✓
  maxReach = max(3, 1+2) = 3  (没有变化)

i=2: 
  2 <= maxReach(3) ✓
  maxReach = max(3, 2+1) = 3  (没有变化)

i=3: 
  3 <= maxReach(3) ✓
  maxReach = max(3, 3+0) = 3  (卡住了！)

i=4: 
  4 > maxReach(3) ✗
  → 无法到达位置4，返回 false

观察：位置3的值是0，这是个"陷阱"。一旦进入，无法跳出。

贪心正确性证明 ​

为什么最远可达就够了？ ​

我们证明：如果存在一条路径能到达终点，那么 maxReach 一定 >= 终点。

证明： 设存在一条可行路径 0 → a₁ → a₂ → ... → 终点。

• 位置 0 能到 a₁，所以 maxReach >= a₁
• 我们能遍历到 a₁（因为 a₁ <= maxReach），更新后 maxReach >= a₂
• 以此类推，maxReach 最终会 >= 终点

所以，只要有路径可达，maxReach 一定能覆盖终点。

复杂度分析 ​

• 时间复杂度：O(n)，一次遍历
• 空间复杂度：O(1)，只用了常量空间

解法二：反向贪心 ​

从终点反向思考：找一个能跳到终点的位置，然后把它作为新的目标。

function canJump(nums: number[]): boolean {
  let goal = nums.length - 1;  // 当前目标位置
  
  for (let i = nums.length - 2; i >= 0; i--) {
    // 如果从位置 i 能跳到 goal
    if (i + nums[i] >= goal) {
      goal = i;  // 新目标变成位置 i
    }
  }
  
  // 如果目标回到了起点，说明可达
  return goal === 0;
}

反向贪心的思路 ​

问题转化：能到达终点 ⟺ 能从起点到达某个"能到终点的位置"

每次找到一个能跳到当前目标的位置，就把它设为新目标。如果最终目标回到起点，说明可达。

两种方法对比 ​

两者时间复杂度相同，都是 O(n)。

常见错误 ​

错误1：没有判断当前位置可达性 ​

// ❌ 错误：没有检查 i 是否可达
function canJump(nums: number[]): boolean {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    maxReach = Math.max(maxReach, i + nums[i]);  // 可能 i 已经不可达
  }
  return maxReach >= nums.length - 1;
}

当数组为 [0, 2, 3] 时，位置0的值是0，无法到达位置1，但上面的代码会错误地返回 true。

错误2：使用 BFS/DFS 导致超时 ​

// ❌ 效率低：指数级复杂度
function canJump(nums: number[]): boolean {
  function dfs(pos: number): boolean {
    if (pos >= nums.length - 1) return true;
    for (let jump = 1; jump <= nums[pos]; jump++) {
      if (dfs(pos + jump)) return true;
    }
    return false;
  }
  return dfs(0);
}

这种方法在大数组上会超时，因为有大量重复计算。

跳跃游戏系列 ​

• 跳跃游戏 I（本题）：判断能否到达
• 跳跃游戏 II：最少跳几次到达
• 跳跃游戏 III：可以向左或向右跳
• 跳跃游戏 IV：可以跳到相同值的位置
• 跳跃游戏 V：带下降限制
• 跳跃游戏 VI：带分数最大化
• 跳跃游戏 VII：只能在特定位置停留

总结 ​

跳跃游戏是理解"可达性分析"的经典问题：

1. 贪心核心：维护"最远可达位置"，不需要记录具体路径
2. 关键判断：当前位置必须在可达范围内
3. 两种视角：正向（扩展可达范围）和反向（收缩目标位置）

这种"能否到达"的问题模式在图论、动态规划中非常常见，掌握贪心思路能帮你快速解决类似问题。