问题45：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例：输入：[2,3,1,1,4] 输出：2
解释：跳到最后一个位置的最小跳跃数是2。从下标为0跳到下标为1的位置，跳1步，然后跳3步到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii

这道题浪费了我大量时间，因为最开始的思路是递归。结果，虽然可以成功处理长度较小的数组，但处理大数组时一直 Time Limit Exceeded。后来，想到一个很巧妙的算法，分享给大家。

第一轮循环

第二轮循环

第三轮循环

其实这个算法本质上就是，设定一个左指针 i ，设定一个左窗格 (i + 1, i + nums[i] + 1) 表示 i 经过第一跳后可以到达的范围，如果数组最后一个节点在此范围内，则成功；否则，在此范围内，寻找范围的最大扩展，将左指针 i 右移到使得下一跳可到达范围最大的节点，并增加一跳，这样循环下去，直至数组最后一个节点在可到达范围内。
被注释起来的几行代码是判断是否可以到达的，就是第55题的要求。加上被注释的几行代码即可判断，如果可以到达，success就会被置1。如果到某处无法继续扩展可到达范围，也就是无解，success的值必定为0，程序就会返回False。

代码如下：

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        i = 0
        c = 0
        while i + nums[i] < len(nums) - 1:
            extend = 0
            #success = 0
            for j in range(i + 1, i + nums[i] + 1):
                if j + nums[j] > extend:
                    pointer = j
                    extend = j + nums[j]
                    #success = 1
                #if success == 0:
                    #return False
            c += 1
            i = pointer
        return c + 1

运行结果：

3

运行结果