题解 | #跳跃游戏(三)#

贪心解法,先判断是否可以走到最后,如果可以,设置 end 为可以跳的最远距离,根据当前位置能跳的最远距离更新 end,代码如下

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
# from queue import PriorityQueue
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        start = n - 1
        for i in range(n - 1, -1, -1):
            if i + nums[i] >= start:
                start = i
            if start == 0:
                return True
        return False
    
    def minJumpStep(self , nums: List[int]) -> int:
        # write code here
#         if not nums: return -1
#         if len(nums) == 1: return 0
#         pq = PriorityQueue()
#         pq.put((-nums[0], 0))
#         s = 0
#         res = 0
#         while not pq.empty() and s < len(nums):
#             x, i = pq.get()
#             s = i - x
#             if s >= len(nums): break
#             res += 1
#             for j in range(i + 1, s + 1):
#                 pq.put((-nums[j], j))
#         if s >= len(nums):
#             return res
#         else:
#             return -1
        if not nums: return -1
        if len(nums) == 1: return 0
        if not self.canJump(nums): return -1
        res = end = pos = 0 
        # 这里的 i < len(nums) - 1, 因为求 res 时 i == end = 0 时 res += 1, 所以到最后一步时不需要再加一步
        for i in range(len(nums) - 1):
            pos = max(pos, nums[i] + i)
            if i == end:
                end = pos
                res += 1
        return res