55. 跳跃游戏#

class Solution {
    public boolean canJump(int[] nums) {
        // maxReach：当前扫描过程中“已知能够到达”的最远下标
        // 初始在起点下标 0，所以最远可达位置先设为 0
        int maxReach = 0;

        // 从左到右遍历位置 i
        // 条件 i <= maxReach 表示：只有当前位置可达时，才有资格继续扩展最远边界
        // 条件 i < nums.length 表示：下标必须在数组范围内
        for (int i = 0; i <= maxReach && i < nums.length; i++) {
            // 从位置 i 最远可以跳到 i + nums[i]
            // 与历史最远可达位置比较，取更大的那个，持续扩大“可达区间”
            maxReach = Math.max(maxReach, i + nums[i]);

            // 提前结束：一旦最远可达位置覆盖末尾下标，说明一定能到达终点
            if (maxReach >= nums.length - 1) {
                // 能到终点，返回 true
                return true;
            }
        }

        // 循环正常结束说明出现“断点”：某个位置不可达，导致无法继续扩展到终点
        return false;
    }

    // 一个更直观但功能相同的版本
    public boolean canJumpAlternative(int[] nums) {
        // energy：把“还能往前走多远”抽象成能量值
        // 初始站在 0 号位置，最多能走 nums[0] 步
        int energy = nums[0];

        // 从第 1 个位置开始尝试前进到末尾
        for (int i = 1; i < nums.length; i++) {
            // 从上一个位置走到当前位置，会消耗 1 点能量
            energy--;

            // 如果能量已经小于 0，说明当前位置不可达，直接失败
            if (energy < 0) {
                return false;
            }

            // 到达当前位置后，可以选择“继承剩余能量”或“使用当前位置提供的最大跳跃能力”
            // 取二者较大值，表示后续可继续前进的最大能力
            energy = Math.max(energy, nums[i]);
        }

        // 能顺利遍历到最后一个位置，说明可以到达终点
        return true;
    }
}

<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="400" fill="#f8f9fa"/>

  <!-- 标题 -->
  <text x="400" y="40" text-anchor="middle" font-size="20" fill="#1976d2">跳跃游戏可视化</text>

  <!-- 数字格子 -->
  <g transform="translate(100,100)">
    <!-- 格子背景 -->
    <rect x="0" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
    <rect x="120" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
    <rect x="240" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
    <rect x="360" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>
    <rect x="480" y="0" width="100" height="100" fill="#2196f3" opacity="0.2"/>

    <!-- 数字 -->
    <text x="50" y="60" text-anchor="middle" font-size="30" fill="#1976d2">2</text>
    <text x="170" y="60" text-anchor="middle" font-size="30" fill="#1976d2">3</text>
    <text x="290" y="60" text-anchor="middle" font-size="30" fill="#1976d2">1</text>
    <text x="410" y="60" text-anchor="middle" font-size="30" fill="#1976d2">1</text>
    <text x="530" y="60" text-anchor="middle" font-size="30" fill="#1976d2">4</text>

    <!-- 跳跃路径 -->
    <path d="M 50 80 C 100 50, 150 50, 170 80" 
          fill="none" stroke="#4caf50" stroke-width="3"/>
    <path d="M 170 80 C 250 20, 350 20, 530 80" 
          fill="none" stroke="#4caf50" stroke-width="3"/>

    <!-- 起点和终点标记 -->
    <circle cx="50" cy="80" r="5" fill="#4caf50"/>
    <circle cx="530" cy="80" r="5" fill="#f44336"/>
  </g>

  <!-- 说明文字 -->
  <g transform="translate(100,250)">
    <text x="0" y="0" font-size="14">最远可达距离的变化：</text>
    <text x="0" y="30" font-size="14">位置0：2步 → 可达位置2</text>
    <text x="0" y="60" font-size="14">位置1：3步 → 可达位置4</text>
    <text x="0" y="90" font-size="14">成功到达终点！</text>
  </g>
</svg>

// 计算到达终点需要的最少跳跃次数
public int minJumps(int[] nums) {
    // jumps：记录已经使用的跳跃次数
    int jumps = 0;
    // currentMax：当前这一次跳跃（当前层）能够覆盖到的最远下标
    int currentMax = 0;
    // nextMax：在当前层内继续扫描时，下一次跳跃能够覆盖到的最远下标
    int nextMax = 0;

    // 遍历到倒数第二个位置即可；最后一个位置不需要再起跳
    for (int i = 0; i < nums.length - 1; i++) {
        // 更新下一层可达的最远边界
        nextMax = Math.max(nextMax, i + nums[i]);
        // 当扫描到当前层边界，说明必须执行一次跳跃进入下一层
        if (i == currentMax) {
            // 跳跃次数 +1
            jumps++;
            // 切换到下一层边界
            currentMax = nextMax;
        }
    }
    // 返回最少跳跃次数
    return jumps;
}