55_跳跃游戏

类型：数组

• 55. 跳跃游戏 💛 ⭐

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

  ❓ 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

  💡 贪心

  对于每一个可以到达的位置 x，它使得 x+1, x+2,…, x + nums[x] 这些连续的位置都可以到达。这样，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。

  在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

  class Solution:
      def canJump(self, nums: List[int]) -> bool:
          furth = 0
          for i in range(len(nums)):
              if i > furth:
                  return False
              furth = max(furth, i + nums[i])
              if furth >= len(nums):
                  return True
          return True

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