最低加油次数

标签: 贪心 数组 动态规划 堆（优先队列）

难度: Hard

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

示例 1：

输入：target = 1, startFuel = 1, stations = []
输出：0
解释：可以在不加油的情况下到达目的地。

示例 2：

输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：无法抵达目的地，甚至无法到达第一个加油站。

示例 3：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠，所以返回 2 。

提示：

  • 1 <= target, startFuel <= 109
  • 0 <= stations.length <= 500
  • 1 <= positioni < positioni+1 < target
  • 1 <= fueli < 109

Submission

运行时间: 29 ms

内存: 16.4 MB

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        n = len(stations)

        h = []
        cnt = 0
        # res = n
        if n ==0:
            return 0 if startFuel>=target else -1
        dist = [stations[0][0]] + [stations[i][0]-stations[i-1][0] for i in range(1, n)] + [target - stations[-1][0]]

        for i in range(n):
            startFuel -= dist[i]
            while startFuel < 0 and h:
                cnt += 1
                t = heappop(h)
                startFuel -= t
            
            if len(h) == 0  and startFuel<0:
                return -1

            heappush(h, -stations[i][1])


        if startFuel - dist[-1] >=0:
            return cnt
        else:
            while len(h)>0:
                t = heappop(h)
                startFuel -= t
                cnt += 1
                if startFuel - dist[-1] >=0:
                    return cnt
                
            return -1

Explain

本题采用贪心算法与优先队列（堆）结合的策略。首先，我们计算从起点到每个加油站以及最后一个加油站到目的地的距离。随着汽车的行驶，我们不断检查剩余燃料。如果在到达下一个加油站前燃料耗尽，我们从之前经过的加油站中选择提供最多燃料的加油站进行加油（这是通过维护一个最大堆实现的，堆中存储的是可以选择的加油站的燃料量）。如果在任何点剩余燃料不足以到达下一个加油站或目的地，且没有更多的加油站可以选择，那么返回-1。若能到达目的地，返回加油次数。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        n = len(stations)

        h = []  # 使用堆来存储可用的燃料
        cnt = 0  # 记录加油次数
        if n == 0:
            return 0 if startFuel >= target else -1  # 如果没有加油站直接判断
        dist = [stations[0][0]] + [stations[i][0] - stations[i-1][0] for i in range(1, n)] + [target - stations[-1][0]]  # 计算各段距离

        for i in range(n):
            startFuel -= dist[i]  # 消耗燃油到达下一站
            while startFuel < 0 and h:  # 如果燃油不足，从堆中取出最大燃油进行加油
                cnt += 1
                t = -heappop(h)
                startFuel += t
            if len(h) == 0 and startFuel < 0:
                return -1  # 如果堆为空且燃油不足，无法继续行驶
            heappush(h, -stations[i][1])  # 将当前加油站燃油加入堆

        if startFuel - dist[-1] >= 0:
            return cnt  # 如果燃油足够到达目的地，返回加油次数
        else:
            while h:  # 否则尝试最后一次加油
                t = -heappop(h)
                startFuel += t
                cnt += 1
                if startFuel - dist[-1] >= 0:
                    return cnt
            return -1  # 如果尝试所有加油后仍无法到达，返回-1

Explore

贪心算法结合优先队列（堆）是处理此问题的有效策略，因为它可以在每个需要加油的时刻选择最优的加油站（即燃料量最大的加油站），确保行驶的持续性和最大化。使用堆结构可以快速、高效地获取最大燃料量的加油站，这是因为堆可以在对数时间内完成插入和删除最大元素的操作。其他算法如动态规划也可以解决此问题，但在处理大量加油站和需要频繁更新的情况下，其时间复杂度和空间复杂度可能不如贪心算法结合优先队列的方法高效。

在实现中，即便汽车在到达某个加油站时剩余燃料为0，只要此时加油站在可到达的范围内（即汽车已经到达了该加油站），汽车仍可以使用该加油站的燃料进行加油。这是因为问题设定中只要到达加油站即可加油，不需要额外的燃料来启动加油过程。因此，只要能够到达加油站，就可以顺利加油继续行驶。

在代码中，如果连续多个加油站的燃料量都无法单独满足到达下一个加油站的需求，算法会利用堆结构继续尝试之前经过且未使用的加油站的燃料。算法持续从堆中取出最大的燃料量进行加油，直到燃料足够到达下一个加油站或堆中没有更多燃料可用。如果堆中的燃料耗尽还是无法到达下一个加油站，那么算法返回-1，表示无法到达目的地。

在Python中，内置的优先队列（heapq）是一个最小堆，它会优先取出最小的元素。为了使得可以优先取出最大的燃料量，解决方案是将燃料量存储为其负值。这样，原本较大的正数燃料值在转为负值后会较小，因此在最小堆中排在前面，被优先取出时，再取其相反数即得到最大的燃料量。这个设计有效地实现了最大堆的功能，以便算法能够每次都能取出当前可用的最大燃料进行加油。