题目描述

N个加油站组成一个环形，给定两个长度都是N的非负数组 oil和dis(N>1)，oil[i]代表 第i个加油站存的油可以跑多少千米，dis[i]代表第i个加油站到环中下一个加油站相隔 多少千米。

假设你有一辆油箱足够大的车，初始时车里没有油。如果车从第i个加油站出发，最终 可以回到这个加油站，那么第i个加油站就算良好出发点，否则就不算。

请返回长度为N的boolean型数组res，res[i]代表第 i 个加油站是不是良好出发点。

输入：

8
gas：4 5 3 1 5 1 1 9
cost：1 9 1 2 6 0 2 0

输出：

0 0 1 0 0 1 0 1

题目解析

暴力

我们可以通过生成辅助数组来验证良好出发点

int[]h

这个数组的长度和cost数组长度一致，且这个数组的每个元素的生成逻辑是：

h[i]=gas[i]-cost[i];

我们可以很容易得到一个结论：h(i) 往后累加，并回到i位置，不出现负数，就是良好出发点 ，这个i位置就是良好出发点。

以每个位置作为i位置，依次走这个逻辑，所以这个解法的复杂度是 O(N^2)，代码如下：

class Solution {
public:
std::vector<bool> canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int N = cost.size();
std::vector<int>helper(N);
for (int i = 0; i < N; ++i) {
helper[i] = gas[i] - cost[i];
}
int pre = 0;
std::vector<bool> ans(N, false);
for (int i = 0; i < N; ++i) {
pre = helper[i];
if (pre < 0) {
continue;
}
for (int j = i + 1; j < N + i + 1; ++j) {
pre += helper[j < N ? j : (j - N)];
if(pre < 0){
break;
}
}
if(pre >= 0){
ans[i] = true;
}
}
return ans;
}
};

滑动窗口

先得到每个点作为起点绕一圈的花费
先生成一个花费数组：$gap[i]-cost[i]$

3	-4	2	-1	-1	1	-1	9

然后生成累加和数组：

3	-1	1	0	-1	0	-1	8

用这个累加和数组再和h[i]数组相加，得到一个两倍长度的数组（这样刚好以每个点作为起点绕一圈）

3	-1	1	0	-1	0	-1	8	11	7	9	8	7	8	7	16

ps：上面过程相当于：

3	-4	2	-1	-1	1	-1	9	3	-4	2	-1	-1	1	-1	9

然后得到累加和：

3	-1	1	0	-1	0	-1	8	11	7	9	8	7	8	7	16

help[i]的意思是：如果从i位置强行去往下一个位置，还剩下多少油。即如果某个元素为负，说明从该位置出发根本无法去往它的下一个节点，如此一来我们就将问题转化成了：求符合“从该位置出发，累加一圈的过程中不出现负数”的所有位置。

也就是：求针对这个数组，滑动窗口为n（n为原数组长度）的最小值，如果第i个窗口内的最小值减去窗口前一个位置的值小于0，则i号位置不是良好出发点

比如

L…L + n - 1是第x个窗口，最小值m，

如果:m - h[L-1] >= 0

则x是良好出发点

反之，则x不是良好出发点, 完整代码：

class Solution {
public:
std::vector<bool> canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int N = cost.size();
int M = N << 1;
std::vector<int>helper(M);
helper[0] = gas[0] - cost[0];
for (int i = 1; i < M; ++i) {
if(i < N){
helper[i] = gas[i] - cost[i];
helper[i] += helper[i - 1];
}
if(i >= N){
helper[i] = helper[i] + helper[i - N];
}
}
std::deque<int> qMin;
std::vector<bool> ans(N, false);
int R = 0, idx = 0, K = N;
while (R < M){
while (!qMin.empty() && helper[qMin.back()] >= helper[R]){
qMin.pop_back();
}
qMin.push_back(R);
while (qMin.front() == R - K){
qMin.pop_front();
}
if(R >= K - 1){
// 窗口已经形成了
if(R == K - 1){
if(helper[qMin.front()] >= 0){
ans[idx] = true;
}
}else{
if(helper[qMin.front()] - helper[R - N] >= 0){
ans[idx] = true;
}
}
idx++;
}
R++;
}
return ans;
}
};

换种写法：

最后

以上就是轻松金鱼最近收集整理的关于算法：加油站的良好出发点问题题目描述题目解析的全部内容，更多相关算法：加油站内容请搜索靠谱客的其他文章。