45. 跳跃游戏 II

        就是在之前的基础上，让每一迭代也就是跳的每一步跳到最远的位置。但是不是到了某个位置就直接向前跳位置最大的距离。因为这不一定是步数最小的步骤。

        下一步的起跳位置应该在上一步可以跳到的范围内，在这个范围内以每一个位置作为起跳点能跳到的最远距离取最大值。这个最大值就是下一步能跳到的最远距离。

        题只要求求出步数，不要求求出具体的跳跃方式，所以要计算步骤，就是遍历的位置，已经超出上一步能跳的范围了，它就已经进行到下一步了。

class Solution:
    def jump(self, nums: List[int]) -> int:
        step=0
        end=0
        max_bound=0
        for i in range(len(nums)-1):
            max_bound=max(max_bound,nums[i]+i)
            if(i==end):
                step+=1
                end=max_bound
        return step

        end是表示上一步能达到的最远位置，这一步起跳点应该在end之前。max_bound表示现在能到达的最远位置，当遍历的起跳点越过end的时候，说明已经进行到下一步了。这个时候这一步能到的最远位置end就是刚才遍历所求的最远位置max_bound。只不过这里并没有记录是从哪一个起跳点跳的。 

  下面这种写法应该更好理解一些：

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums)<=1:
            return 0
        step = 0
        reach = 0
        start = 0
        farest = 0
        i=0
        # 最后一个点已经在可以到达的范围内就可以停止了
        while reach<len(nums)-1:
            for i in range(start,reach+1):
                farest = max(farest,nums[i]+i)
            start = reach+1
            reach = farest
            step+=1
        return step

每一步的起跳点都是在[start，reach]中选取，fareast遍历在这些起跳点里能到达的最远距离。那么下一步的起跳点就要从[reach+1，fareast]中选取。也就是说更新start=reach+1，reach = farest。为啥要从reach+1开始找下一步的起跳点？因为reach前面的点都已经跳过了，而且[reach+1，fareast]中间的点肯定是能跳到的。