LeetCode 871. 最低加油次数

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 微软
标签
数组 动态规划 贪心 堆（优先队列）

题目描述

✅ 871. 最低加油次数

image-20260928225236201

image-20260928225236204

题意分析

从位置 0 出发，每行驶一单位距离消耗一单位油，油箱容量不限。每站可以选择不停，或停一次取走全部油，要求到达终点的最少停靠次数。站点已按位置递增排列，恰好耗尽油到达站点时仍可加油，恰好到达终点也算成功。

解法：贪心 + 最大堆

核心思路

[!blue]

用 fuel 表示从起点出发、使用已选择站点的油后能到达的最远坐标，而不是车在某处的剩余油量。它初始为 startFuel，每选择一站就直接加上该站油量，无需逐段扣除路程。将位置 <= fuel 的所有未处理站点油量放入最大堆；它们都已经可达，但还没有被选为停靠站。

只要 fuel < target，就至少还需要一次加油，并且新增补给必须先来自当前范围内的站点，否则根本到不了那个站。堆中任意一站都只花一次停靠，选油量最大的站能使新范围至少和其他选择一样远，也不会失去后续站点。因此将下一次较小油量选择换成堆顶不会增加所需次数，可以反复做这个贪心选择。

从堆中选中较早的站点，表示补上“经过它时停靠”的决定，并不要求车辆倒退。该站本来就可达，提前携带这些油也没有容量限制；所选站点按位置顺序实际经过即可。每次扩大范围后，先把新可达站点全部加入，再决定下一次加油，避免漏掉油量更大的新候选。

到达 target 后立即停止，继续加油只会多算次数。若尚未到达而堆已为空，意味着所有可达补给都已用完，更远站点也无法接近，只能返回 -1。

解题步骤

  1. 初始化最远可达坐标 fuel = startFuel、站点下标 idx = 0、停靠次数 stops = 0。
  2. 当 fuel < target 时，将从 idx 开始所有位置不超过 fuel 的站点加入最大堆，并推进下标，保证每站只入堆一次。
  3. 堆为空则返回 -1；否则弹出最大油量，加到 fuel，并将停靠次数加 1。
  4. 可达范围覆盖终点后返回次数。初始油量已经足够时循环不执行，返回 0；站点下标到头时，只要堆里仍有油，就应继续尝试。

代码实现

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;
    }
}

import "container/heap"

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+1)+1)$，各站至多入堆、出堆一次。
  • 空间复杂度：$O(n+1)$，候选最大堆。

关键点总结

[!green]

  • 变量表示最远可达坐标，不是当前位置的剩余油量。
  • 入堆只登记机会，弹出才计加油次数。

易错点总结

[!yellow]

  • 最小堆会优先选收益较小的停靠。
  • 不包含位置等于可达边界的站，会错失刚好能到的加油机会。
  • 站点指针到头就判断失败，会忽略堆里仍未使用的油。

相似题目

题目 难度 关联与区别
502. IPO 困难 同样先纳入当前可达门槛的资源，再用最大堆选择能带来最大增益者。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/40069970
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！