871_最低加油次数

类型：堆

1. 最低加油次数 ❤️
https://leetcode-cn.com/problems/minimum-number-of-refueling-stops/

❓ 数组 station 存储了加油站信息，station[i] = [d, f] 表示在距离起点 d 公里处的地方有加油站，站内有 f 升油。汽车从起点出发，假设其油箱容量无限，最初装有 startFuel 升油，1 升油可走 1 公里。求问，为了到达目的地，汽车至少加多少次油？若无法到达目的地，则返回 - 1.

💡 堆（事后诸葛亮）

我们假设完全不加油，看能开到多远。如果能直接到达目的地，那直接就成功了，如果不能到达，我们把油耗光的这个点叫做失败点。要在失败点之前「至少」要加一次油才行，我们自然就选尽量大的加油站。经过加油后，我们又到达了下一个失败点，说明除了上个失败点之前加的几次油外，我们在新的失败点之前还得加油，同样我们还是尽量从大的加油站加。就这样一直省着加，挑最大的加，直到到达（或到不了）目的地。

此处还有一个小窍门，我们把目的地也当作一个加油站，把它放在 stations 列表的末尾，这样可以简化逻辑。
```
class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations += [(target, 0)]
        ans = 0
        lastPos = 0
        h = []
        cur = startFuel
        for i, fuel in stations:
            # 如果到这里还有油，那就不想加油的事
            cur -= i - lastPos

            while cur < 0 and h:
                cur -= heapq.heappop(h)
                ans += 1
            if cur < 0:
                return -1

            lastPos = i
            heapq.heappush(h, -1 * fuel)
        return ans
```