题目描述

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

沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。

当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

样例

输入：target = 1, startFuel = 1, stations = []
输出：0
解释：我们可以在不加油的情况下到达目的地。

输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：我们无法抵达目的地，甚至无法到达第一个加油站。

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
我们出发时有 10 升燃料。
我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。
我们沿途在1两个加油站停靠，所以返回 2 。

注意

• 1 <= target, startFuel, stations[i][1] <= 10^9
• 0 <= stations.length <= 500
• 0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

算法1

(动态规划) $O(n^2)$

1. $f(i,j)$ 表示经过了 $i$ 个加油站，加了 $j$ 次油之后的最大剩余油量。为了方便写代码，可以在开头（下标为 0 ）和结尾（下标为 n + 1）加入油量为 0 的加油站。
2. 初始值 $f(0, 0)=startFuel$，其余都为 -1。
3. 到达一个加油站后，如果决定不加油，则更新 $f(i,j) = max(f(i,j), f(i - 1,j) - (stations[i][0] - stations[i - 1][0]))$；如果决定加油，则需要判断 $f(i-1,j-1) \ge stations[i][0] - stations[i - 1][0]$，即保证能到达第 $i$ 个加油站后，则更新 $f(i, j) = max(f(i, j), f(i - 1, j - 1) - (stations[i][0] - stations[i - 1][0]) + stations[i][1])$。不加油不需要判断因为如果到不了第 $i$ 个加油站，$f(i,j)$ 就不会更新为大于等于 0 的数字。
4. 最终答案为找到最小的 $j$ 使得 $f(n+1,j) \ge 0$。这里将终点记为第 $n+1$ 个加油站即可。

时间复杂度

• 共 $O(n^2)$ 个状态，每次两种转移，故时间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size();

        vector<vector<int>> f(n + 2, vector<int>(n + 2, -1));
        stations.insert(stations.begin(), {0, 0});
        stations.push_back({target, 0});

        f[0][0] = startFuel;

        for (int i = 1; i <= n + 1; i++)
            for (int j = 0; j <= i; j++) {
                f[i][j] = max(f[i][j], f[i - 1][j] - (stations[i][0] - stations[i - 1][0]));
                if (j > 0 && f[i - 1][j - 1] >= stations[i][0] - stations[i - 1][0])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] - (stations[i][0] - stations[i - 1][0]) + stations[i][1]);
            }

        for (int i = 0; i <= n; i++)
            if (f[n + 1][i] >= 0)
                return i;

        return -1;
    }
};

算法2

(贪心，堆) $O(n \log n)$

1. 使用变量 $remain$ 记录当前的油量。在路过一个加油站时，我们先不做决定是否需要加油，等到到了某个加油站发现，$remain$ 已经变成负数了，此时从之前经过的加油站中，挑选油量最多的若干个加油站加油。
2. 具体来说，维护一个大根堆，在到达一个加油站时，如果 $remain$ 变为了负数，则需要从堆中取出若干个加油站加油使得 $remain$ 变为非负。如果堆空了还不能使得 $remain$ 变为非负，则返回 -1。$remain$ 变为了非负之后，将当前加油站的油量放入大根堆中。
3. 为了方便写代码，可以在开头（下标为 0 ）和结尾（下标为 n + 1）加入油量为 0 的加油站。

时间复杂度

• 每次维护堆的复杂度为 $O(\log n)$，一共有 $O(n)$ 次维护，所以总时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size(), remain, ans;
        priority_queue<int> heap;

        stations.insert(stations.begin(), {0, 0});
        stations.push_back({target, 0});

        remain = startFuel;
        ans = 0;
        for (int i = 1; i <= n + 1; i++) {
            remain -= stations[i][0] - stations[i - 1][0];
            while (remain < 0 && !heap.empty()) {
                remain += heap.top();
                heap.pop();
                ans++;
            }
            if (remain < 0)
                return -1;
            heap.push(stations[i][1]);
        }
        return ans;
    }
};