Cocolib

Appearance

On this page

跳跃游戏 II ​

Question

给定一个长度为n的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • ``i + j < n`

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

思路 ​

关键是理解覆盖范围的概念，这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

45.跳跃游戏II
js
var jump = function(nums) {
    if(nums.length===1) return 0
    let cur = 0     //当前的覆盖范围
    let next = 0    //下一步的覆盖范围
    let res = 0
    for(let i=0; i<nums.length; i++){
        next = Math.max(next,nums[i]+i)     
        if(i===cur){
            if(cur!=nums.length-1){	
                res++
                cur = next
            }
            if(cur>=nums.length-1)
                return res
        }
    }
    return res
};