最低加油次数

2024-10-07

题目：

汽车从起点出发驶向目的地，该目的地位于出发位置东面 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

思路：

这道题如果以模拟思维去做，就需要用到动态规划：
	通过定义dfs函数，去判断如果汽车能行驶到某个加油站，加不加油。
	然后对于所有可以选择的加油站，取最小加油次数
	需要有的数据结构包括：
		记忆[当前位置][当前油量]到达target的最小加油次数的记忆化数组
		深搜的dfs函数

模拟思维是最为直接，且最为直观的思考方式，但是这道题可以换成贪心思维。
由于汽车行驶完当前油量可以途径很多加油站，那么我就当做获取油桶了，加不加油先不管，等到后续有加油需求再加。

当汽车行驶到第 i 个加油站时，视作获取了一个装有 fuel_i 升汽油的油桶。
在后续的行驶过程中，可以在没油时，把油桶中的油加到汽车中。
选哪个（哪些）油桶？
	为了让加油次数尽量少，贪心地选油量多的油桶。
	由于有添加和删除操作，用最大堆维护这些油桶。

细节
可以把终点 target 视作一个虚拟加油站，加到 stations 末尾，这样可以用同样的代码处理最后一段路程（从最后一个加油站到终点）。

可以提前判断 startFuel ≥ target 的情况，油量足以把车开到终点，直接返回 0。或者，在循环中判断 curFuel ≥ target − position_i 的情况，此时可以退出循环。不过考虑到对实际运行时间没有影响，代码中没有写这些优化。

代码：

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        stations.push_back({target, 0});
        int ans = 0, pre_position = 0, cur_fuel = startFuel;
        priority_queue<int> fuel_heap;
        for (auto& station : stations) {
            int position = station[0];
            cur_fuel -= position - pre_position; // 每行驶 1 英里用掉 1 升汽油
            while (!fuel_heap.empty() && cur_fuel < 0) { // 没油了
                cur_fuel += fuel_heap.top(); // 选油量最多的油桶
                fuel_heap.pop();
                ans++;
            }
            if (cur_fuel < 0) { // 无法到达
                return -1;
            }
            fuel_heap.push(station[1]); // 留着后面加油
            pre_position = position;
        }
        return ans;
    }
};