45. Jump Game II

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个数字数组 nums

数组中每一个元素代表如果当前站在这个格子上的话最多可以往前跳几格

初始状态下我们在下标 0 的位置

题目要求我们计算出最少需要经过几次跳跃才能到达数组末尾元素

解题思路

题目要求我们使用最少次跳跃跳到数组末尾，我们可以用贪心的思路来解决这个问题

假设我们有个数组是：[2,3,1,1,4]

我们的策略是：对每一个元素，我们都在它可以跳的范围内选择下一步可以跳的最远的元素

假设 cur 是当前我们遍历的元素的下标，以下是操作步骤：

1. cur = 0：此时我们能跳的最远的下标是 2，我们用一个临时变量 farthest 标记
2. 我们从可以跳到的元素中选择能跳最远的元素（也就是元素 3，下标 1），更新 cur
3. cur = 1：此时我们能跳的最远的下标是 4，我们用 farthest 标记
4. farthest 命中了数组末尾元素，结束遍历

代码如下：

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
    const len = nums.length
    let cur = 0
    let next = 0
    let steps = 0

    while (next < len - 1) {
        let farthest = 0
        for (let i = cur; i <= next; i++) {
            farthest = Math.max(farthest, i + nums[i])
        }
        steps++
        cur = next + 1
        next = farthest
    }

    return steps
};