难度: Medium
给定一个长度为 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]。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000nums[n-1]运行时间: 64 ms
内存: 15.9 MB
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
end = 0
jumps = 0
farthest = 0
for i in range(n-1):
farthest = max(farthest, i+nums[i])
if end == i:
jumps += 1
end = farthest
return jumps
这个题解使用贪心算法的思想。我们维护两个变量：当前能够到达的最远位置 `end`，和下一步能够到达的最远位置 `farthest`。在遍历数组的过程中，如果当前位置 `i` 超过了 `end`，说明我们必须再跳一步，并且将 `end` 更新为 `farthest`。这样，我们就能计算出到达最后一个位置所需的最小跳跃次数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
end = 0 # 当前能够到达的最远位置
jumps = 0 # 跳跃次数
farthest = 0 # 下一步能够到达的最远位置
for i in range(n-1):
farthest = max(farthest, i+nums[i]) # 更新下一步能够到达的最远位置
if end == i: # 如果当前位置已经是当前能够到达的最远位置
jumps += 1 # 则需要再跳一步
end = farthest # 更新当前能够到达的最远位置
return jumps
在更新`farthest`时，使用`max(farthest, i + nums[i])`是为了确保在遍历过程中始终保持`farthest`为当前能达到的最远距离。这是因为`farthest`需要考虑从当前位置之前的所有位置跳跃能达到的最远距离，而不仅仅是当前位置的跳跃结果。如果简单地将`farthest`设置为`i + nums[i]`，将会忽略之前可能更远的跳跃目标，导致不能正确计算最远到达距离。
此策略不会导致数组中的某些位置不被检查。算法确保在`end`到达之前，每个位置都被考虑过。如果`i`达到`end`，这意味着我们已经达到了当前跳的最远范围，必须进行下一次跳跃以继续前进。在这之前，所有小于等于`end`的位置都已经被考虑过，所以不会有遗漏。
在循环中不包括最后一个数组元素是因为当我们的`end`达到或超过最后一个位置时，我们已经可以保证到达终点，而不需要再对最后一个元素进行操作。实际上，循环的目的是更新到达每个位置的最远范围和所需的跳跃次数，一旦我们的`end`已经覆盖了最后一个位置，就不需要再进一步增加跳跃次数或更新范围。
如果数组中的零导致无法向前跳跃到达数组末尾，则这种贪心算法无法成功。例如在数组`[3,2,1,0,4,0,0]`中，尽管开始的跳跃可达到较远的位置，但如果零位于关键位置（如示例中的位置4，且无法从前面的位置跳过此位置），则跳跃将停止，无法到达数组末端。算法在遇到这种情况时不会返回有效的跳跃次数，而是应该指示无法完成任务。