[LeetCode] 871. Minimum Number of Refueling Stops

[grandyang]

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations.  Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it.  It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination?  If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there.  If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation:
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

Note:

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

这道题说有一辆小车，需要向东行驶 target 的距离，路上有许多加油站，每个加油站有两个信息，一个是距离起点的距离，另一个是可以加的油量，问我们到达 target 位置最少需要加的油量。我们可以从第三个例子来分析，开始时有 10 升油，可以到达第一个加油站，此时花掉了 10 升，但是可以补充 60 升，当前的油可以到达其他所有的加油站，由于已经开了 10 迈，所以到达后面的加油站的距离分别为 10，20，和 50。若我们到最后一个加油站，那离起始位置就有 60 迈了，再加上此加油站提供的 40 升油，直接就可以到达 100 位置，不用再加油了，所以总共只需要加2次油。由此可以看出来其实我们希望到达尽可能远的加油站的位置，同时最好该加油站中的油也比较多，这样下一次就能到达更远的位置。像这种求极值的问题，十有八九要用动态规划 Dynamic Programming 来做，但是这道题的 dp 定义式并不是直接来定义需要的最少加油站的个数，那样定义的话不太好推导出状态转移方程。正确的定义应该是根据加油次数能到达的最远距离，我们就用一个一维的 dp 数组，其中 dp[i] 表示加了i次油能到达的最远距离，那么最后只要找第一个i值使得 dp[i] 大于等于 target 即可。dp 数组的大小初始化为加油站的个数加1，值均初始化为 startFuel 即可，因为初始的油量能到达的距离是确定的。现在来推导状态转移方程了，遍历每一个加油站，对于每个遍历到的加油站k，需要再次遍历其之前的所有的加油站i，能到达当前加油站k的条件是当前的 dp[i] 值大于等于加油站k距起点的距离，若大于等于的话，我们可以更新 dp[i+1] 为 dp[i]+stations[k][1]，这样就可以得到最远能到达的距离。当 dp 数组更新完成后，需要再遍历一遍，找到第一个大于等于 target 的 dp[i] 值，并返回i即可，参见代码如下：
解法一：

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size();
        vector<long> dp(n + 1, startFuel);
        for (int k = 0; k < n; ++k) {
            for (int i = k; i >= 0 && dp[i] >= stations[k][0]; --i) {
                dp[i + 1] = max(dp[i + 1], dp[i] + stations[k][1]);
            }
        }
        for (int i = 0; i <= n; ++i) {
            if (dp[i] >= target) return i;
        }
        return -1;
    }
};

这道题还有一个标签是 Heap，说明还可以用堆来做，这里是用最大堆。因为之前也分析了，我们关心的是在最小的加油次数下能达到的最远距离，那么每个加油站的油量就是关键因素，可以将所有能到达的加油站根据油量的多少放入最大堆，这样每一次都选择油量最多的加油站去加油，才能尽可能的到达最远的地方（如果骄傲没被现实大海冷冷拍下，又怎会懂得要多努力，才走得到远方。。。打住打住，要唱起来了 ^o^）。这里需要一个变量i来记录当前遍历到的加油站的位置，外层循环的终止条件是 startFuel 小于 target，然后在内部也进行循环，若当前加油站的距离小于等于 startFuel，说明可以到达，则把该加油站油量存入最大堆，这个 while 循环的作用就是把所有当前能到达的加油站的油量都加到最大堆中。这样取出的堆顶元素就是最大的油量，也是我们下一步需要去的地方（最想要去的地方，怎么能在半路就返航？！），假如此时堆为空，则直接返回 -1，表示无法到达 target。否则就把堆顶元素加到 startFuel 上，此时的startFuel 就表示当前能到的最远距离，是不是跟上面的 DP 解法核心思想很类似。由于每次只能去一个加油站，此时结果 res 也自增1，当 startFuel 到达 target 时，结果 res 就是最小的加油次数，参见代码如下：
解法二：

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int res = 0, i = 0, n = stations.size();
        priority_queue<int> pq;
        for (; startFuel < target; ++res) {
            while (i < n && stations[i][0] <= startFuel) {
                pq.push(stations[i++][1]);
            }
            if (pq.empty()) return -1;
            startFuel += pq.top(); pq.pop();
        }
        return res;
    }
};

Github 同步地址:

#871

参考资料：

https://leetcode.com/problems/minimum-number-of-refueling-stops/

https://leetcode.com/problems/minimum-number-of-refueling-stops/discuss/149839/DP-O(N2)-and-Priority-Queue-O(NlogN)

https://leetcode.com/problems/minimum-number-of-refueling-stops/discuss/149858/Simple-Java-Solution-Using-PriorityQueue-O(nlogn)

LeetCode All in One 题目讲解汇总(持续更新中...)