45_跳跃游戏_II

类型：数组

• 45. 跳跃游戏 II 💛 ⭐

  https://leetcode-cn.com/problems/jump-game-ii/

  ❓ 数组中的元素表示你在该位置可以跳跃的最大长度，问从数组首最少跳跃几次可到达数组尾。

  💡 贪心

  我们从数组首出发，维护当前能够到达的最大下标位置，记为边界。遍历边界内的元素，找到最远的跳跃距离(下标+跳跃长度)，更新为新的边界。每次更新边界都是一次跳跃，跳跃次数加一。我们不需要遍历到最后一个元素，到倒数第二个就行了。因为我们计算的是「起跳」的次数，我们并不会在最后一个元素起跳。

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

  时间复杂度：O(N)，空间复杂度：O(1)