跳跃游戏

    数组 贪心

    题目描述

    给定一个非负整数数组 steps，其中每个元素代表你在该位置可以跳跃的最大长度。最初你站在数组的第一个位置，判断你是否能够到达最后一个位置。

    思路分析

    本题的核心在于：你能否通过每一步的最大跳跃能力，最终到达或超过终点。最直接的做法是递归或动态规划，但最优解是贪心。

    贪心思路：

    • 用 maxReach 记录当前能到达的最远下标。
    • 遍历每个位置：
      • 如果当前位置已超出 maxReach，说明无法到达，直接返回 false。
      • 每次用 i + steps[i] 更新 maxReach。
      • 如果 maxReach 已覆盖终点，立即返回 true。
    • 循环结束还没覆盖终点，返回 false。

    这种贪心策略只需一次遍历，效率极高。

    示例代码

    /**
 * @param steps - 每个位置最大可跳跃步数的数组
 * @returns 是否可以到达最后一个位置
 *
 * @example
 * canJump([2,3,1,1,4]) // true
 * canJump([3,2,1,0,4]) // false
 */
export function canJump(steps: number[]): boolean {
    // 记录当前能到达的最远下标
    let maxReach = 0;

    // 遍历每个位置
    for(let i = 0; i < steps.length; i++) {
        // 如果当前位置已超出最远可达范围，说明无法到达
        if(i > maxReach){
            return false;
        }

        // 更新最远可达下标
        maxReach = Math.max(maxReach, i + steps[i]);

        // 如果最远可达下标已覆盖终点，提前返回 true
        if(maxReach >= steps.length - 1){
            return true;
        }
    }

    // 循环结束还没覆盖终点，返回 false
    return false;
}

    复杂度分析

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

    示例演示

    以 steps = [2, 3, 1, 1, 4] 为例，核心步骤如下：

    位置 (i)steps[i]maxReach是否可达备注
    022是初始位置
    134是maxReach 更新为 4，已覆盖终点
    • 第 0 步，maxReach = max(0, 0 + 2) = 2。
    • 第 1 步，maxReach = max(2, 1 + 3) = 4，此时已覆盖终点，返回 true。

    再看一个无法到达的例子：steps = [3, 2, 1, 0, 4]

    • 走到下标 3 时，maxReach = 3，但 steps[3] = 0，无法再前进，终点无法到达，返回 false。