LeetCode 55.跳跃游戏：贪心策略下的可达性判断

一、问题定义与核心挑战

1.1 问题描述

给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素 nums[i] 表示你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

1.2 核心特征与难点

• 跳跃规则：从位置 i 出发，可跳到 i+1、i+2、…、i+nums[i] 中的任意位置（不超过数组边界）
• 可达性判断：无需记录具体路径，只需判断终点是否可达
• 高效性要求：暴力枚举所有路径会超时，需找到贪心或动态规划的优化解法

示例：

• 输入：nums = [2,3,1,1,4] → 输出：true（路径：0→1→4）
• 输入：nums = [3,2,1,0,4] → 输出：false（最远只能到索引3，无法到达4）

二、解题思路：贪心算法的最大覆盖范围

2.1 核心思想

贪心算法的关键在于跟踪当前可到达的最大范围（覆盖范围），并通过不断扩展覆盖范围来判断终点是否可达：

• 局部最优：在当前覆盖范围内，找到能跳得最远的位置（即 i + nums[i] 最大）
• 全局最优：持续扩展覆盖范围，若覆盖范围包含终点，则返回 true；若遍历完当前覆盖范围仍未到达终点，则返回 false

2.2 直观理解

可以将数组想象成一段需要跨越的区域，每个位置 i 能提供一个“辐射范围” [i, i+nums[i]]：

• 初始时，辐射范围从 0 开始（cover = 0）
• 遍历辐射范围内的每个位置，计算其能到达的最远距离，更新辐射范围
• 若辐射范围扩展到包含终点（nums.length - 1），则成功；若辐射范围无法再扩展且未包含终点，则失败

三、代码逐行解析

3.1 边界条件处理

if (nums.length <= 1) {
    return true;
}

• 若数组长度为0或1（起点即终点），必然可达，直接返回 true。

3.2 核心变量与遍历逻辑

int cover = 0;  // 当前可到达的最大索引（覆盖范围）

// 遍历当前覆盖范围内的所有位置
for (int i = 0; i <= cover; i++) {
    // 扩展覆盖范围：取当前位置能到达的最远距离与现有覆盖范围的最大值
    cover = Math.max(i + nums[i], cover);
    
    // 若覆盖范围已包含终点，直接返回true
    if (cover >= nums.length - 1) {
        return true;
    }
}

3.3 最终判断

return false;  // 遍历完所有可达位置仍未到达终点，返回false

四、算法执行过程演示

4.1 示例1：nums = [2,3,1,1,4]

• 初始：cover = 0，遍历 i=0（在覆盖范围内）
  • i + nums[i] = 0 + 2 = 2 → cover 更新为 2
  • 覆盖范围 [0,2] 未包含终点（4），继续遍历
• i=1（在覆盖范围内）
  • i + nums[i] = 1 + 3 = 4 → cover 更新为 4
  • 覆盖范围 [0,4] 包含终点（4）→ 返回 true

4.2 示例2：nums = [3,2,1,0,4]

• 初始：cover = 0，遍历 i=0
  • i + nums[i] = 0 + 3 = 3 → cover 更新为 3
  • 覆盖范围 [0,3] 未包含终点（4），继续遍历
• i=1（在覆盖范围内）
  • i + nums[i] = 1 + 2 = 3 → cover 保持3
• i=2（在覆盖范围内）
  • i + nums[i] = 2 + 1 = 3 → cover 保持3
• i=3（在覆盖范围内）
  • i + nums[i] = 3 + 0 = 3 → cover 保持3
• 遍历结束（i=4 超出覆盖范围 3），未到达终点 → 返回 false

五、核心逻辑深度解析

5.1 为什么遍历范围是 i <= cover？

cover 表示当前能到达的最远索引，只有在这个范围内的位置 i 是可达的，其跳跃才能被纳入考虑。超出 cover 的位置尚未可达，无需遍历。

5.2 为什么 cover = Math.max(i + nums[i], cover) 能保证最优？

• i + nums[i] 是位置 i 能到达的最远距离
• 取最大值确保覆盖范围始终是当前可达的最大范围，体现了“贪心”思想（每次都选择能跳得最远的选项）

5.3 为什么无需回溯？

贪心算法的特点是“只看当前最优，不回头”。本题中，一旦覆盖范围确定，所有在范围内的位置都已被考虑，无需回溯到之前的位置重新判断，因为扩展后的覆盖范围已包含了所有可能的更优选择。

六、算法复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。最坏情况下，需遍历到覆盖范围的边界（最多为 n-1），但每个元素仅被访问一次。
• 空间复杂度：O(1)，仅使用常数个变量（cover、i），与输入规模无关。

七、常见误区与优化说明

7.1 误区1：尝试记录具体路径

题目只需判断可达性，无需记录路径。试图记录路径会增加空间复杂度（如使用数组或列表存储路径），且无必要。

7.2 误区2：遍历所有元素而非覆盖范围

若错误地遍历整个数组（i < nums.length），而非限制在 i <= cover，会导致访问不可达的位置，虽然结果可能正确，但会降低效率（尤其当覆盖范围远小于数组长度时）。

7.3 优化点：提前终止判断

在每次更新 cover 后立即判断是否包含终点，可在早期终止循环（如示例1中，i=1 时已覆盖终点，无需继续遍历 i=2）。

八、总结：贪心算法在跳跃问题中的应用

本题的贪心解法通过跟踪最大覆盖范围，高效判断终点可达性，核心在于：

1. 范围更新：在当前可达范围内，不断扩展最大覆盖范围
2. 早期终止：一旦覆盖范围包含终点，立即返回结果
3. 效率优势：线性时间复杂度，常数空间复杂度，远超暴力枚举的性能

这种“覆盖范围扩展”的思路可推广到其他可达性问题（如 Jump Game II 求最少跳跃次数），是贪心算法解决范围优化类问题的典型范例。