跳跃游戏-ii

Tips

题目类型: Greedy

相关题目:

• 55. 跳跃游戏
• 435. 无重叠区间
• 452. 用最少数量的箭引爆气球

题目

给定一个非负整数数组, 你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 假设你总是可以到达数组的最后一个位置.

提示:

• 1 <= nums.length <= 10⁴
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n - 1]

示例

输入: [2, 3, 1, 1, 4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2. 从下标为 0 跳到下标为 1 的位置, 跳 1 步, 然后跳 3 步到达数组的最后一个位置.

题解

核心思想: 每次都跳到当前能跳到的最远位置, 这样可以保证用最少的步数到达终点.

• 维护两个指针:

  • end: 当前能跳到的最远位置.
  • maxReachableIndex: 在当前能跳到的范围内, 能跳到的最远位置.

• 遍历数组:

  • 当遍历到 end 时, 说明已经跳到了一个新的能跳到的最远位置, 更新 end 为 maxReachableIndex.
  • 同时更新 maxReachableIndex, 寻找下一个能跳到的最远位置.

• 跳跃次数: 每更新一次 end, 就代表跳了一次.

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  const n = nums.length
  let end = 0
  let maxReachableIndex = 0
  let jumps = 0

  // 注意是 n - 1
  for (let i = 0; i < n - 1; i++) {
    maxReachableIndex = Math.max(maxReachableIndex, i + nums[i])

    if (i === end) {
      // 遇到边界, 必须要跳一次了, 就更新边界, 并且步数加一
      end = maxReachableIndex
      jumps++
    }
  }
  return jumps
}

Rust

use std::cmp;

pub fn jump(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut maxReachableIndex = 0;
    let mut end = 0;
    let mut jumps = 0;

    for i in 0..(n - 1) {
        maxReachableIndex = cmp::max(maxReachableIndex, nums[i] + i as i32);

        if i as i32 == end {
            end = maxReachableIndex;
            jumps += 1;
        }
    }

    jumps
}