题目描述

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;}
};

换种写法：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！