44. Jump Game II 跳跃游戏II

做完 Jump Game，再来看看这个题目。

题目

给定一个非负数组 nums，你一开始在数组的第一个索引。
数组中的每个元素表示你在该位置可以跳的最大距离。
你的目标是以最少的跳跃次数，到达最后一个索引。
你可以认为你总能到达最后一个索引。

解析

还是以 [2,3,1,1,4,6,3,5,8,1] 为例子，我们只需要确定每一跳能到达的最大位置，然后就可以得到跳跃到最终索引的最大位置了。

1. 开始 i=0
2. 第一跳的最大位置是 i+nums[i] = 2，所以第一跳的最大位置是 2。
3. 然后我们需要计算第二跳的最大位置，第二跳的最大位置，应该在 0 ～ 2（包含）之间产生，遍历 i = [0,1,2]，计算
   i+nums[i]。得到第二跳的最大位置是 4。此时我们得到第一跳最大位置 2,第二跳最大位置 4。
4. 同样的，第三跳的最大位置，将在以第一跳最远距离和第二跳最远距离之间的某一个跳板上产生。`因为在第一跳最远距离之前的点上，其跳跃的最远距离是第二跳的最远距离，不能再突破了。
5. 如果在遍历第二跳的最远距离时，发现第二跳最远距离始终小于或等于第一跳最远距离，说明后续的节点已经不可达了。

所以，我们需要三个指针，分别指向 上一次跳跃的最大位置，当前跳跃的最大位置，下一次跳跃的最大位置。
我们还需要一个游标，在上一次跳跃和当前跳跃间移动，以更新下一次跳跃的最大位置，寻找完成后，步数+1, 三个指针分别递进。

伪代码

var last，cur，next
fo i<=cur
    next = max(i+nums[i])
step+=1
if next >= len(nums)-1
    return step

代码

func jump(nums []int) int {
    if len(nums)==1 {
        return 0
    }
    var last, cur, next, step int
    for cur<len(nums) {
        for i:=last;i<=cur;i++ {
            if i+nums[i] > next {
                next = i+nums[i]
            }
            if next >= len(nums)-1{
                return step+1
            }
        }
        step+=1
        last = cur
        cur = next
    }
    return step
}

image.png