871. 最低加油次数

exiaohu 于 2022-07-02 发布

题目链接:871. 最低加油次数

想象成不是只在加油站才能加油,而是只要现在需要油,并且之前有加油站还没有加油,那么此时就可以加油。

这样一来,如果要使得加油次数最少,那么只要加油就加最多的油。

为了保证时间效率,这里用堆来维护前面的未用过的加油站里的油量。

需要加油而没有油时,那么就不能够到达,此时返回-1。

import heapq
from collections import deque
from typing import List


class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations, seen_stations, pos, cnt = deque(sorted(stations)), [], startFuel, 0
        while True:
            if pos >= target:
                return cnt

            while stations and stations[0][0] <= pos:
                _, fuel = stations.popleft()
                heapq.heappush(seen_stations, -fuel)

            if not seen_stations:
                return -1

            pos -= heapq.heappop(seen_stations)
            cnt += 1