[LeetCode]Minimum Number of Refueling Stops

看到这道题的第一个思路是BFS，类似Jump Game II，每一层中我们在所有可以到达的加油站当中取油最多的。比如靠着startfuel我们可以到达0，1，2三个加油站，并且加油站1的油最多，所以第一次我们选择在1加油。那么在1加完油之后我们继续重复上面的步骤。但是这个方法是有一个问题的，比如target为110，startfuel为10，stations为[[5, 30], [10, 80], [100, 1]]这种情况，我们第一次能到达0和1的加油站，我们取1，加80的油。但是再从这开始重复以上的步骤的话，我们最多只能加1的油，而无法到达target。这里我们可以明显看到我们算法的问题，这里我们只考虑了1之后的加油站，而实际上我们应该考虑所有可以到达还没有选择的加油站当中最多的。明确了这个思路之后，我们就可以改良我们的算法，我们用priority_queue维护所有我们经过的还没有选择的stations的储油的量，每一次我们发现油用光了并且还没有到达target中的时候，就取得pq的顶端的加油站对应的油。这样保证我们每一次取的都是在可以到达的范围内没有取过的最多的油。时间复杂度O(n * log n)，空间复杂度O(n)。代码如下：

	class Solution {
	public:
	int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
	stations.push_back({target, 0});
	int len = stations.size(), steps = 0, prev = 0;
	long remain = startFuel;
	priority_queue<int> pq;
	for (int i = 0; i < len; ++i)
	{
	int curr = stations[i][0], fuel = stations[i][1];
	remain -= curr - prev;
	while (pq.size() && remain < 0)
	{
	remain += pq.top();
	pq.pop();
	++steps;
	}
	if (remain < 0)return -1;
	pq.push(fuel);
	prev = curr;
	}
	return steps;
	}
	};

view raw Minimum Number of Refueling Stops_pq.cpp hosted with ❤ by GitHub

这道题用DP也是当然可以解的，我们用dp[i]表示加了i次油之后能到达最远的点。那么dp[i + 1]就等于所有location小于等于dp[i]的加油站中还没有选过的最多的油和dp[i]的和。换句话说，对于stations[i]和所有dp[j]，where 1 <= j <= i && stations[i][0] <= dp[j - 1]，dp[j] = max(dp[j], dp[j - 1] + stations[i][1])。时间复杂度为O(n^2)，具体实现的方式可能不同。代码如下：

写法一：

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

view raw Minimum Number of Refueling Stops_dp1.cpp hosted with ❤ by GitHub

写法二：

	class Solution {
	public:
	int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
	int len = stations.size();
	vector<long> dp(len + 1, 0);
	dp[0] = startFuel;
	unordered_set<int> visited;
	for (int i = 1; i <= len; ++i)
	{
	int j = 0, idx = -1;
	while (j < len && stations[j][0] <= dp[i - 1])
	{
	if(visited.find(j) == visited.end())
	idx = idx == -1 || stations[j][1] > stations[idx][1] ? j : idx;
	++j;
	}
	if (idx == -1)return -1;
	visited.insert(idx);
	dp[i] = dp[i - 1] + stations[idx][1];
	}
	for (int i = 0; i <= len; ++i)
	if (dp[i] >= target)return i;
	return -1;
	}
	};

view raw Minimum Number of Refueling Stops_dp2.cpp hosted with ❤ by GitHub