871.最低加油次数

链接：871.最低加油次数
难度：Hard
标签：贪心、数组、动态规划、堆（优先队列）
简介：为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

题解 1 - python

• 编辑时间：2024-10-07
• 执行用时：52ms
• 内存消耗：16.74MB
• 编程语言：python
• 解法介绍：贪心，每次走到最大距离时，加一次最多的加油站的油

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations.append([target, 0])
        res = 0
        cur = startFuel
        q = []
        for pos, fuel in stations:
            while q and cur < pos:
                res += 1
                cur += -heappop(q)
            if cur < pos: return -1
            heappush(q, -fuel)
        return res