[LeetCode 871] Minimum Number of Refueling Stops

题目

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 stations represents a gas station that is stations[i][0] miles east of the starting position, and has stations[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]

---

思路

问题求最少停靠次数，最能直接想到的办法就是把所有能到达终点的停靠方案都求解出来，选最少的方案。但是这个方法需要遍历所有的停靠方案，复杂度可能是O(k^n)。

从另一个角度思考这个问题。停靠0次，是否能到达终点；停靠1次，是否能到达终点；…；停靠n次是否能到达终点。n最多为500，因此该方案只需要判断O(n)次是否能到达终点就求解了。

判断能否到达终点的方案则是记录这次停靠前最远能跑多远，然后在能到达的站点中选一个油量最多的站点停靠，那么就是当前停靠次数最远的距离，这个距离到达终点的话则返回当前停靠次数即可。

如果没到达，那就需要再停靠一次，即再选择一个油量最多的站点。通过遍历的方式来选择的话时间复杂度是O(n)，可以通过维护一个最大堆来降低时间复杂度。维护的时间复杂度为O(logn)，因此，总的时间复杂度为O(nlogn)。

---

Code in C++

class Solution {    
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {

        priority_queue<int> candidates; // maxinum heap

        int stops = 0;
        int cursor = 0;
        int distance = startFuel;

        while (distance < target) {
            while (cursor < stations.size() && stations[cursor][0] <= distance) {
                candidates.push(stations[cursor++][1]);
            }
            if (candidates.empty()) 
                return -1;

            distance += candidates.top();
            candidates.pop();
            ++stops;
        }
        return stops;
    }
};

---

性能

---

优化方案

• 如果考虑空间复杂度，可以采用DP，时间复杂度为O(n^2)，但是空间复杂度降低为O(nlogn)