跳跃游戏

Tips

题目类型: Greedy

相关题目:

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

题目

给定一个非负整数数组 nums, 你最初位于数组的第一个下标. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 判断你是否能够到达最后一个下标.

提示:

• 1 <= nums.length <= 3 * 10⁴
• 0 <= nums[i] <= 10⁵

示例

输入: nums = [2, 3, 1, 1, 4]
输出: true
解释: 可以先跳 1 步, 从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标.

输入: nums = [3, 2, 1, 0, 4]
输出: false
解释: 无论怎样, 总会到达下标为 3 的位置. 但该下标的最大跳跃长度是 0, 所以永远不可能到达最后一个下标.

题解

我们把这个题转化一下, 变成按照题目的规则, 最多能跳多远, 如果能越过最后一个, 返回 true, 否则返回 false. 因此这道题就变成了动态规划, 因为是在求最值嘛.

什么是贪心算法呢? 每一步都计算一下从当前位置最远能够跳到哪里, 然后和一个全局最优的最远位置 maxPosition 做对比, 通过每一步的最优解, 更新全局最优解, 这就是贪心.

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
  const n = nums.length
  let maxPosition = 0

  for (let i = 0; i < n - 1; i++) {
    // 不断计算能跳到的最远距离
    maxPosition = Math.max(maxPosition, i + nums[i])

    // 可能碰到了 0, 卡住跳不动了
    if (maxPosition <= i) return false
  }

  return maxPosition >= n - 1
}

Rust

use std::cmp;

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

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

        if max_position <= i as i32 {
            return false;
        }
    }

    max_position >= (n - 1) as i32
}