LeetCode 871. 最低加油次数

2021-04-02 HGNULB 约 9 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 871. 最低加油次数

题意分析

一辆车从位置 $0$ 出发，油箱里已有 startFuel 单位燃料，要开到位置 target。每单位燃料恰好走一英里，油箱容量无限。沿途有若干加油站，第 $i$ 个写成 [position, fuel]，表示它在 position 处，油量是 fuel，可以选择停或不停，停了就把这一整箱油全灌进去。

要求的是「最少停几次」，不是「最省油」也不是「最快」。这句话决定了目标函数只数停靠次数，每一站的油量只是达成这个次数的手段。

有两个约束信号很关键。其一，题目保证 stations 已经按 position 严格递增排好，所以不需要额外排序，可以直接用一个指针从左往右推进。其二，油箱容量无限，意味着加油的先后顺序不影响油量总和——只要一批加油站都在你走过的路上，先加哪一个、后加哪一个，最终油量完全一样。这一条是后面所有推理的地基。

规模上，加油站最多 500 个，target 和各站油量都不超过 $10^9$。$n$ 很小，$O(n^2)$ 的做法其实也能过，但面试要的是 $O(n \log n)$。

边界要想清楚三处：stations 可能为空，此时能否到达完全取决于 startFuel 是否已经不小于 target；起点油量可能连第一个加油站都够不着，直接无解；恰好 startFuel == target 时答案是 $0$，不能多加一次。

解法：贪心 + 最大堆

核心思路

先想暴力。每个加油站都是「停」或「不停」的二选一，枚举所有子集是 $2^n$，显然不行。改成动态规划会好一些：设 $f[j]$ 表示「恰好加了 $j$ 次油时能到达的最远位置」，从左到右扫加油站，对每个站倒序更新 $f[j] = \max(f[j], f[j-1] + fuel_i)$（前提是 $f[j-1] \ge position_i$）。最后找最小的 $j$ 使 $f[j] \ge target$。这是正确的，代价 $O(n^2)$。

瓶颈在于：动态规划把「每一种加油次数」的最优状态全都存了下来，但我们只关心最少次数。有没有办法只沿一条路径走？

关键观察来自题意里那句「加油顺序不影响总量」。既然如此，我们完全可以先假装一路开过去，把途经的每个加油站的油量都记在一个候选池里，先不真的加。只有当油不够、车要抛锚时，才回过头从候选池里挑一箱油「补加」进去——反正它就在已经走过的路上，事后补加和当时就加在数学上等价。而既然每次补加都要付出「停靠次数加一」的代价，那就应该挑池子里油最多的那一箱，这样一次代价换来的续航最长。这就是所谓的后悔贪心：先不做决定，等被迫时才用最优的历史选项来兑现。

于是核心不变量是这样两条。第一，变量 fuel 恒等于「在当前已经付出的 stops 次加油代价下，车能到达的最远位置」——注意它不是「剩余油量」，而是一个绝对坐标，因为起点是 $0$ 且一单位油走一英里，两者数值刚好重合，用坐标表述能省掉一个「当前位置」变量。第二，最大堆里装的恰好是「位置不超过 fuel、但还没有被兑现」的所有加油站油量。每当 fuel 增大，就要立刻把新变得可达的站补进堆，让第二条不变量继续成立。

有了这两条，终止条件就自然了：fuel >= target 说明已经能开到终点，返回 stops；堆空却仍有 fuel < target，说明所有能触及的加油站都已用尽，再也无法前进，返回 $-1$。

解题步骤

建一个最大堆，初始化 fuel = startFuel、指针 idx = 0、计数 stops = 0。为什么用最大堆：每次兑现都要付出固定的一次停靠代价，代价相同就该取收益最大的那个。

进入主循环，条件是 fuel < target。为什么用严格小于：fuel == target 时车已经能滑到终点，再加油就多算一次。

循环开头先做「入堆」：只要 idx 没越界且 stations[idx][0] <= fuel，就把 stations[idx][1] 压进堆并让 idx 前进。为什么条件带等号：加油站正好落在当前能到达的最远点上时，车是能停下加油的，漏掉等号会误判无解。

为什么入堆写在循环体内而不是循环外：每次兑现都会抬高 fuel，之前够不着的加油站可能变得可达，必须在下一轮判断前把它们补进候选池，否则不变量被破坏。

检查堆是否为空。空则说明可达范围内的油全用光了还到不了终点，直接返回 $-1$。为什么这时才判无解：判早了会把「还有站没入堆」的情况误杀，判晚了会在空堆上取元素而崩溃。

弹出堆顶的最大油量累加到 fuel，stops 自增一。为什么在出堆时计数而不是入堆时：入堆只是「路过并记下」，没有付出代价；真正的加油动作发生在弹出的那一刻。

循环自然退出时返回 stops。

以 target = 100、startFuel = 10、stations = [[10,60],[20,30],[30,30],[60,40]] 走一遍：初始 fuel = 10、idx = 0、stops = 0、堆空。第一轮，$10 < 100$ 进入循环；入堆阶段 stations[0] 的位置 $10 \le 10$ 成立，压入 $60$，idx 变 $1$；stations[1] 的位置 $20 > 10$，停止入堆，此时堆为 ${60}$。堆非空，弹出 $60$，fuel 变成 $70$，stops 变成 $1$。第二轮，$70 < 100$；入堆阶段依次判断位置 $20 \le 70$ 压入 $30$（idx 变 $2$）、位置 $30 \le 70$ 压入 $30$（idx 变 $3$）、位置 $60 \le 70$ 压入 $40$（idx 变 $4$），堆变成 ${40, 30, 30}$。弹出堆顶 $40$，fuel 变成 $110$，stops 变成 $2$。第三轮判断 $110 \ge 100$，循环结束，返回 $2$。注意堆里剩下的两个 $30$ 从头到尾没被用上，这正是「先不决定、被迫时才兑现」带来的收益。

代码实现

// 当燃料不足以到达下一个位置时，从堆中取最大油量补充。
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        int fuel = startFuel;
        int idx = 0;
        int stops = 0;

        while (fuel < target) {
            while (idx < stations.length && stations[idx][0] <= fuel) {
                maxHeap.offer(stations[idx][1]);
                idx++;
            }

            if (maxHeap.isEmpty()) {
                return -1;
            }

            fuel += maxHeap.poll();
            stops++;
        }

        return stops;
    }
}

// 当燃料不足以到达下一个位置时，从堆中取最大油量补充。
type MaxHeap []int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func minRefuelStops(target int, startFuel int, stations [][]int) int {
    h := &MaxHeap{}
    heap.Init(h)
    fuel := startFuel
    idx := 0
    stops := 0

    for fuel < target {
        for idx < len(stations) && stations[idx][0] <= fuel {
            heap.Push(h, stations[idx][1])
            idx++
        }

        if h.Len() == 0 {
            return -1
        }

        fuel += heap.Pop(h).(int)
        stops++
    }

    return stops
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 $n$ 是加油站数量。每个加油站至多入堆一次、出堆一次，各自 $O(\log n)$；指针 idx 单调右移，全程只扫一遍数组；外层循环的次数不超过出堆次数，也就不超过 $n$。

空间复杂度：$O(n)$，最坏情况下所有加油站都可达且都还没兑现，堆里同时存着 $n$ 个油量，其余变量都是常数级。

关键点总结

后悔贪心的模板长这样：先把所有路过的机会存进候选池，不急着做选择；等到被迫必须付出代价时，再从池子里取收益最大的那个兑现。适用前提是「选择顺序不影响结果」，本题靠油箱无限容量保证了这一点。

把 fuel 定义成「能到达的最远坐标」而不是「剩余油量」，是这道题代码短的根本原因：省掉了「当前位置」变量，也省掉了每段路程的扣减，一个量同时承担了两个角色。

候选池的维护必须和主状态联动。fuel 一变大，就要立刻把新可达的加油站补进堆——把入堆写在循环外面是最常见的结构性错误。

无解的判据是「候选池空」而非「指针到头」。这两者不等价：指针没到头但后面的站都在可达范围之外时，池子已经空了。

面试视角：先给出 $O(n^2)$ 的「$f[j]$ 表示加 $j$ 次油能到的最远位置」这版动态规划，再用「加油顺序无关」推出后悔贪心，是最完整的答题路径。只甩一个堆出来，面试官通常会追问为什么贪心是对的。

易错点总结

错误写法：用最小堆，或者把 Java 比较器写成 (a, b) -> a - b。用例 target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]，每次挑最小的一箱油，停靠次数会变成 3 甚至更多，答案偏大。

错误写法：入堆条件写成 stations[idx][0] < fuel，漏掉等号。同一个用例里第一个加油站位置正好是 $10$，等于 startFuel，会被跳过，堆立刻为空，函数错误地返回 $-1$。

错误写法：主循环条件写成 fuel <= target。当 startFuel 恰好等于 target 时会白白加一次油，本该返回 $0$ 却返回 $1$。

错误写法：把入堆的内层循环挪到主循环外面只执行一次。第二轮之后 fuel 已经抬高，位置 $20$、$30$、$60$ 的三个站永远进不了候选池，能到达的用例会被判成 $-1$。

错误写法：无解判据写成 idx >= stations.length 才返回 $-1$。当所有站都已入堆并被榨干、fuel 仍够不到终点时，条件不成立，主循环会在空堆上反复取元素，抛异常或死循环。

错误写法：先弹堆再判空。堆为空时 poll() 返回 null，自动拆箱直接抛空指针；Go 里则会在空切片上越界。

错误写法：stops 在入堆时自增。这样统计的是「路过了几个加油站」，用例中路过 4 个站却只加了 2 次油，答案会变成 4。

错误写法：同时维护「当前位置」和「剩余油量」两个变量，却在加油时忘了把位置推进到该加油站。剩余油量会被重复计算，fuel 虚高，可能把无解的输入判成有解。

错误写法：stations 为空时特判成返回 $0$。若 startFuel < target 且没有任何加油站，正确答案是 $-1$；直接让主循环走一遍空堆分支才是对的。

相似题目

题目	难度	考察点
630. 课程表 III	困难	同为后悔贪心，但兑现方式是「反悔」：先全部选上，超时后从堆里弹出耗时最长的课退掉
502. IPO	困难	同为「可达集合随状态增长而扩张 + 最大堆取收益」，但扩张条件是资本阈值，且限制了总操作次数
253. 会议室 II	中等	用的是最小堆，堆里存的是结束时间而非收益，目标是求并发峰值而不是最少操作数