最低加油次数 图解题解

这道题到底在问什么

target

100

startFuel

10

stations

[[10,60],[20,30],[30,30],[60,40]]

输出

2

最优解：一步一步想明白

1. 3因为加油站只要开过去就永远能用(它的油一直在那等你),所以不必当场决定。攒着,等卡住了再补——而且每次都补油最多的那个,这样补的次数一定最少。
2. 4盯住下面三样怎么变:车的油量 fuel(能开多远 = 当前油量)、指针 ptr(沿路把开过的加油站油量记进堆)、大根堆(堆顶永远是攒下的最大那桶油)。
3. 5起步油 fuel=10,加油次数 stops=0加油站本来就按位置升序给好。车从 0 出发,起步油 10——也就是最远只能开到位置 10。最后一格是终点 100。指针 ptr 沿路往右,把够得着的加油站油量记进堆。
4. 6fuel=10:位置 10 的 s0 够得着 → 记进堆起步油 10,车最远开到位置 10,正好够到 s0。把它的油量 60 记进堆(先不加,攒着)。再看 s1 在位置 20,油 10 开不到,指针先停下。
5. 7fuel=10 开到位置 10 就空了,还没到 100起步油 10 全烧光,车只到位置 10 就开不动了,离终点 100 还差得远(后面的站都够不着,变灰)。但堆里攒着 s0 的油 60,该取出来加上了。
6. 8堆里现在:[60]经过 s0,把它的油量 60 记进堆(堆 = 攒下还没用的油)。堆顶永远是攒下的里最大的那桶。现在油 10 到不了终点 100,也开不到下一站,必须从堆里取油。
7. 9pop 堆顶 60 → fuel = 10 + 60 = 70油不够,就从堆顶取攒下最大的那桶 60 加进油箱,油从 10 涨到 70,加油次数 +1。油变多了,原本开不到的加油站这下都够得着——回去推指针继续记账。
8. 10fuel=70:覆盖 s1/s2/s3,但还差终点油涨到 70,车一口气能开到位置 70——绿勾标出的 s1、s2、s3 全在射程内,接下来要把它们的油都记进堆。但终点 100 还在 70 之外,记完仍得再取一次油。
9. 11fuel=70:位置 20 的 s1 够得着 → 记进堆油涨到 70,车最远能开到位置 70。指针往右推:s1 在 20,够得着,油量 30 记进堆。s0 已用过(灰)。70 还能开更远,接着看下一个。
10. 12堆里现在:[30]s1 的油 30 记进堆。但记账阶段还没结束——油 70 也开得到位置 30 的 s2,先把沿途够得着的全记进来,再决定要不要取油。
11. 13fuel=70:位置 30 的 s2 也够得着 → 记进堆油 70 也开得到 s2(位置 30),油量 30 一起记进堆。这一段一口气记了两个站。再往右看 s3 在位置 60,油 70 也够——继续推。
12. 14新油量 30 先放末尾:[30, 30]入堆分两步。第一步:新油量 30 先塞到堆的最末尾。它和父亲 30 一样大,没有「比父亲大」,所以不违反大根堆规矩,不用往上冒。
13. 15堆里现在:[30, 30],无需上浮s2 的 30 就位了——它不比父亲大,留在堆底当孩子,堆依然合法。现在堆里攒了两桶 30。油 70 还能开到 s3,先把它也记进来,再决定取哪桶。
14. 16fuel=70:位置 60 的 s3 也够得着 → 记进堆油 70 还够得着 s3(位置 60),油量 40 记进堆。指针走到加油站末尾,沿途能记的全记完了。但油 70 仍开不到终点 100,所以还得取油。
15. 17新油量 40 先放末尾:[30, 30, 40]新油量 40 先挂到堆的最末尾,它的父亲是堆顶的 30。40 比父亲 30 大,违反了「大根堆父亲最大」的规矩,所以下一帧要让 40 往上冒。
16. 1840 与父亲 30 交换,冒到堆顶:[40, 30, 30]第二步「上浮」:新来的 40 和父亲 30 比,40 更大就交换、一路往上冒,直到比父亲小或到顶。这里 40 一步就冒到了堆顶,原来的 30 沉下去当孩子。这就是堆维持「堆顶最大」的内部动作。
17. 19所有站记完,fuel=70 < target=100 → 再取油沿途的加油站全记进堆了(s1、s2、s3),指针到头。可油 70 还是到不了终点 100(终点变灰)。堆里攒着 30、30、40 三桶,该取最大的 40 加上。
18. 20拿走 40,末尾 30 搬到堆顶:[30, 30]取堆顶分两步。第一步:把堆顶 40 拿走做掉(加进油箱),再把末尾的 30 搬到堆顶补空。现在堆顶临时是 30,接下来要让它和孩子比、必要时一路「下沉」。
19. 2130 无更大的孩子,停在顶 → fuel = 70 + 40 = 110补到顶的 30 不比孩子小,停在顶上,堆依然合法。第一步拿走的 40 加进油箱,油从 70 涨到 110,已经 ≥ 100,到终点了!加油次数 = 2。堆里剩的两桶 30 没机会用了。
20. 22油轨迹 10 →(+60) 70 →(+40) 110 ≥ 100整道题就是这个循环:能开多远就把沿途加油站油量记进堆,开不动了就取堆顶最大那桶。绿勾标出真正加油的两个站(s0 的 60、s3 的 40),油一路 10 → 70 → 110,答案 2,和手算一致。
21. 23别一经过加油站就加(会浪费次数),也别只挑近的加——决定加哪桶的永远是油量大小。攒着,卡住再取最大,这就是「反悔型贪心」:先记下所有可能,等需要时挑最优的兑现。
22. 24认出这类题的信号:① 候选随某个单调量(位置/本金/时间)逐步「解锁」;② 每次只需要候选里的最大或最小。一旦命中,就是「排序解锁 + 堆取极值」,502 / 630 都是它。
23. 25O(n²) → O(n log n)核心提速:用大根堆替代每次卡住重扫。每个加油站一生只进堆一次、出堆一次,取最大油只要 O(log n),不再做重复劳动。
24. 29油开不到下一站、堆里也没攒下油如果油不够开到任何还没记的加油站,堆又是空的(没攒下任何油可取),就说明永远到不了终点,必须返回 -1,不能硬去取空堆。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import heapq
class Solution:
    def minRefuelStops(self, target, startFuel, stations):
        heap = []          # 取负油量压小根堆,模拟大根堆
        fuel, stops, i = startFuel, 0, 0
        n = len(stations)
        while fuel < target:
            while i < n and stations[i][0] <= fuel:  # 沿途记进堆
                heapq.heappush(heap, -stations[i][1])
                i += 1
            if not heap:   # 卡住又无油可取 → 到不了
                return -1
            fuel += -heapq.heappop(heap)  # 取最大那桶油
            stops += 1
        return stops

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> heap;   // 大根堆:攒下的油量
        long fuel = startFuel;
        int stops = 0, i = 0, n = stations.size();
        while (fuel < target) {
            while (i < n && stations[i][0] <= fuel) {  // 沿途记进堆
                heap.push(stations[i][1]);
                i++;
            }
            if (heap.empty()) return -1;
            fuel += heap.top(); heap.pop();   // 取最大那桶油
            stops++;
        }
        return stops;
    }
};

import java.util.*;
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        long fuel = startFuel;
        int stops = 0, i = 0, n = stations.length;
        while (fuel < target) {
            while (i < n && stations[i][0] <= fuel) {  // 沿途记进堆
                heap.offer(stations[i][1]);
                i++;
            }
            if (heap.isEmpty()) return -1;
            fuel += heap.poll();   // 取最大那桶油
            stops++;
        }
        return stops;
    }
}

复杂度

面试官可能追问