跳跃游戏-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 步到达数组的最后一个位置.

题解

我们贪心的从前往后寻找, 每次去找最远的位置. 以 nums = [2, 3, 1, 2, 4, 2, 3] 为例: 从下标 0 向后出发, 它可以跳到下标 1 的位置, 下一次最多可跳 3 步; 也可以跳到下标 2 的位置, 但下次最多只可跳 1 步, 因此第一次我们选择跳到下标 1 的位置. 从下标 1 向后出发, 它可以跳到下标 2, 3, 4 的位置, 显然跳到下标 4, 下次跳的更多, 因此这次选择跳到下标 4 的位置...

在具体的实现中, 我们维护当前能够到达的最大下标位置, 记为边界. 我们从左到右遍历数组, 到达边界时, 更新边界并将跳跃次数增加 1.

在遍历数组时, 我们不访问最后一个元素, 这是因为在访问最后一个元素之前, 我们的边界一定大于等于最后一个位置, 否则就无法跳到最后一个位置了. 如果访问最后一个元素, 在边界正好为最后一个位置的情况下, 我们会增加一次不必要的跳跃次数, 因此我们不必访问最后一个元素.

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  const n = nums.length
  let end = 0
  let maxPosition = 0
  let steps = 0
  for (let i = 0; i < n - 1; i++) {
    // 不断计算能跳到的最远距离
    maxPosition = Math.max(maxPosition, i + nums[i])

    // 如果恰好为最后一个位置, 需要增加一次 step, 以越过最后一个
    if (i === end) {
      end = maxPosition
      steps++
    }
  }
  return steps
}

Rust

use std::cmp;

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

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

        if i as i32 == end {
            end = max_position;
            step += 1;
        }
    }

    step
}