跳跃游戏 II

    数组 贪心

    题目描述

    给定一个非负整数数组 nums，每个元素代表你在该位置可以跳跃的最大长度。最初你站在数组的第一个位置，请你计算到达数组最后一个位置的最少跳跃次数。

    思路分析

    关键在于如何用最少的步数到达终点。我们可以采用贪心策略：每一步都尽可能跳到当前能到达的最远位置。遍历数组时，维护两个变量：farthest 表示当前能跳到的最远下标，currentEnd 表示本次跳跃的边界。

    当遍历到边界时，说明需要进行一次新的跳跃，并更新边界为 farthest。每次跳跃都选择覆盖范围最大的区间，这样可以保证步数最少。只要边界覆盖了终点，就可以提前结束循环。整个过程只需一次遍历，且每一步的决策都是局部最优，从而达到全局最优。

    示例代码

    /**
 * @param nums - 非负整数数组，每个元素代表最大可跳步数
 * @returns 最少跳跃次数
 *
 * 示例：
 * 输入: [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到下标 1（跳 1 步），再跳 4（跳 3 步），共 2 步到达终点。
 */
export function jump(nums: number[]): number {
  let steps = 0; // 记录跳跃次数
  let farthest = 0; // 当前能跳到的最远位置
  let currentEnd = 0; // 当前这一步能到达的边界

  // 遍历到倒数第二个元素即可，最后一步一定能到终点
  for (let i = 0; i < nums.length - 1; i++) {
    // 更新当前能跳到的最远位置
    farthest = Math.max(farthest, i + nums[i]);

    // 如果到达了当前边界，需要跳一次，并更新边界
    if (i === currentEnd) {
      steps++;
      currentEnd = farthest;
    }
    // 如果最远边界已经覆盖终点，可以提前结束
    if (currentEnd >= nums.length - 1) {
      break;
    }
  }

  return steps;
}

    复杂度分析

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

    示例演示

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

    位置 (i)nums[i]farthestcurrentEndsteps备注
    02201第一次跳跃，边界到 2
    13422第二次跳跃，边界到 4，已覆盖终点
    • 第 0 步，farthest = max(0, 0 + 2) = 2，到达边界 0，跳跃一次，currentEnd = 2。
    • 第 1 步，farthest = max(2, 1 + 3) = 4，到达边界 2，跳跃一次，currentEnd = 4，已覆盖终点。

    最终只需 2 步即可到达终点。