Hard

题目描述

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

沿途有加油站，每个加油站由 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 次加油停留，所以我们返回 2。

提示：

  • 1 <= target, startFuel <= 10^9
  • 0 <= stations.length <= 500
  • 1 <= positioni < positioni+1 < target
  • 1 <= fueli < 10^9

解题思路

这是一道贪心算法的经典题目。核心思想是：当燃料不足时，总是选择之前经过的加油站中燃料最多的那个进行加油。

贪心策略分析：

  • 我们尽可能地向前行驶，直到燃料不足以到达下一个加油站或目的地
  • 当燃料不足时，从之前经过但未使用的加油站中选择燃料最多的进行"回溯加油"
  • 这样能保证用最少的加油次数获得最多的燃料

算法流程：

  1. 使用最大堆存储经过但未使用的加油站的燃料量
  2. 模拟行驶过程：
    • 将当前能到达的所有加油站加入堆中
    • 如果当前燃料无法到达目的地，从堆中取出燃料最多的加油站进行加油
    • 重复直到能到达目的地或堆为空

为什么贪心策略是正确的？ 因为我们总是在最需要燃料时选择获得最多燃料的加油站，这样能最大化每次加油的效果，从而最小化加油次数。

其他解法：

  • 动态规划：定义 dp[i] 为加油 i 次能到达的最远距离，时间复杂度 O(n²)
  • 本题推荐贪心+堆的解法，时间复杂度更优

代码实现

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> maxHeap;  // 存储经过的加油站的燃料量
        int fuel = startFuel;
        int position = 0;
        int refuels = 0;
        int i = 0;
        
        while (position + fuel < target) {
            // 将当前能到达的所有加油站加入堆
            while (i < stations.size() && stations[i][0] <= position + fuel) {
                maxHeap.push(stations[i][1]);
                i++;
            }
            
            // 如果没有可用的加油站，返回-1
            if (maxHeap.empty()) {
                return -1;
            }
            
            // 选择燃料最多的加油站加油
            fuel += maxHeap.top();
            maxHeap.pop();
            refuels++;
        }
        
        return refuels;
    }
};

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        import heapq
        
        max_heap = []  # Python的heapq是最小堆，用负数模拟最大堆
        fuel = startFuel
        position = 0
        refuels = 0
        i = 0
        
        while position + fuel < target:
            # 将当前能到达的所有加油站加入堆
            while i < len(stations) and stations[i][0] <= position + fuel:
                heapq.heappush(max_heap, -stations[i][1])  # 用负数模拟最大堆
                i += 1
            
            # 如果没有可用的加油站，返回-1
            if not max_heap:
                return -1
            
            # 选择燃料最多的加油站加油
            fuel += -heapq.heappop(max_heap)
            refuels += 1
        
        return refuels

public class Solution {
    public int MinRefuelStops(int target, int startFuel, int[][] stations) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        int fuel = startFuel;
        int position = 0;
        int refuels = 0;
        int i = 0;
        
        while (position + fuel < target) {
            // 将当前能到达的所有加油站加入堆
            while (i < stations.Length && stations[i][0] <= position + fuel) {
                maxHeap.Enqueue(stations[i][1], stations[i][1]);
                i++;
            }
            
            // 如果没有可用的加油站，返回-1
            if (maxHeap.Count == 0) {
                return -1;
            }
            
            // 选择燃料最多的加油站加油
            fuel += maxHeap.Dequeue();
            refuels++;
        }
        
        return refuels;
    }
}

var minRefuelStops = function(target, startFuel, stations) {
    const maxHeap = new MaxPriorityQueue();
    let fuel = startFuel;
    let position = 0;
    let stops = 0;
    let i = 0;
    
    while (position + fuel < target) {
        while (i < stations.length && stations[i][0] <= position + fuel) {
            maxHeap.enqueue(stations[i][1]);
            i++;
        }
        
        if (maxHeap.isEmpty()) {
            return -1;
        }
        
        const maxFuel = maxHeap.dequeue().element;
        fuel += maxFuel;
        stops++;
    }
    
    return stops;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log n)，其中 n 是加油站数量。每个加油站最多被加入和移出堆一次，堆操作的时间复杂度为 O(log n)
空间复杂度O(n)，最坏情况下需要将所有加油站都加入堆中