题目描述
给定一个长度为 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]。
思路
第一时间想到的肯定是贪心算法呀，假如跳跃的右边界为 r，当前位置为 i，在 r 之前我们可以计算此时的 i+nums[i] 的最大值。当遍历到 r 时执行跳跃，更新 r 的值即可。
因为生成的样例一定会到达终点，因此循环条件只需要到倒数第二个元素即可，否则如果 r 的值恰好等于最有一个元素的位置，就会增加一次额外的跳跃。
最终代码：
class Solution:
def jump(self, nums: List[int]) -> int:
right = 0
maxD = 0
cnt = 0
for i, num in enumerate(nums[:-1]):
maxD = max(maxD, num+i)
if i==right:
cnt, right = cnt+1, maxD
return cnt