问题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
运行结果
