134. Gas Station
Medium
There areNgas stations along a circular route, where the amount of gas at stationiisgas[i].
You have a car with an unlimited gas tank and it costscost[i]of gas to travel from stationito its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the
circuit once in the clockwise direction, otherwise return -1.
Note:
If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:
Input:gas = [1,2,3,4,5]cost = [3,4,5,1,2]Output:3Explanation:Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4Travel to station 4. Your tank = 4 - 1 + 5 = 8Travel to station 0. Your tank = 8 - 2 + 1 = 7Travel to station 1. Your tank = 7 - 3 + 2 = 6Travel to station 2. Your tank = 6 - 4 + 3 = 5Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.Therefore, return 3 as the starting index.
Example 2:
Input:gas = [2,3,4]cost = [3,4,3]Output:-1Explanation:You can't start at station 0 or 1, as there is not enough gas to travel to the next station.Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4Travel to station 0. Your tank = 4 - 3 + 2 = 3Travel to station 1. Your tank = 3 - 3 + 3 = 3You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.Therefore, you can't travel around the circuit once no matter where you start.
思路：
维护一个当前油量变量，当它走一圈之间，任何时间点出现负值，就说明失败；否则成功。看看从哪个节点开始走，出现成功，就返回那个节点。
空间复杂度：O（1）
时间复杂度：O（n的平方）
代码：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for (int judgingStation = 0; judgingStation < gas.size(); judgingStation++) {
if (canCompleteStartFromStation(gas, cost, judgingStation)) {
return judgingStation;
}
}
return -1;
}
bool canCompleteStartFromStation(vector<int>& gas, vector<int>& cost, int startStation) {
int remainingOil = 0;
for (int i = 0; i < gas.size(); i++) {
int currentStation = (startStation + i) % gas.size();
remainingOil += gas.at(currentStation) - cost.at(currentStation);
if (remainingOil < 0) return false;
}
return true;
}
};
结果：
Runtime:292 ms, faster than3.65%of C++ online submissions for Gas Station.
Memory Usage:9.1 MB, less than100.00%of C++ online submissions for Gas Station.
能不能做到时间空间都排名第一？
很遗憾，自己没能想出优化方案。但是网友想到了（还是网友强大（笑cry.jpg
思路是，从第一个加油站开始算起，一直往下走，就算油箱空了也继续，不够油就记为负数。找到最后一个油箱最小值的位置，再往后一个位置就是可以走一圈的位置了。
我的C++代码如下
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int minTank = INT_MAX;
int minTankStation = -1;
int tank = 0;
for (int i = 0; i < gas.size(); i++) {
tank += gas.at(i) - cost.at(i);
if (tank <= minTank) {
minTankStation = i;
minTank = tank;
}
}
if (tank < 0) { return -1; }
else { return (minTankStation + 1) % gas.size(); }
}
};
为什么这种方法有效呢？
我们假设可行的入口前面不是tank的最小值。那么说面馆可行入口的前面其实也是一个可行入口。按照题意，我们题目只有一个入口，不会出现两个。所以可行入口的前面一定是最小值。
但是别人是怎么能想到tank最小值的这个办法的呢？
去网上看别人的博客，看到一句段，很有道理：
假设开始设置起点start = 0, 并从这里出发，如果当前的gas值大于cost值，就可以继续前进，此时到下一个站点，剩余的gas加上当前的gas再减去cost，看是否大于0，若大于0，则继续前进。当到达某一站点时，若这个值小于0了，则说明从起点到这个点中间的任何一个点都不能作为起点，则把起点设为下一个点，继续遍历。当遍历完整个环时，当前保存的起点即为所求。（来自https://www.cnblogs.com/grandyang/p/4266812.html(1)）
看到这里恍然大悟：假设从p点，走到了q点，还没够一圈，但是已经耗尽了油。p点加油站gas-cost>0这是肯定的。p为起点是，到达p+1的时候汽车是有剩余油量的（gas[p]-cost[p])，然而就算有剩余油量，往后走也走不过q点。可想而知，直接从q点出发，一开始剩余油量为0<=gas[p]-cost[p]，就完全不可能到达q点以后的点了。【3】
这样就引出了一个线性时间复杂度的算法。
但是这个算法的复杂度是O(2n) (可以参考这篇文章的分子https://www.cnblogs.com/felixfang/p/3814463.html#4185270(2)）
为什么是O(2n)？因为从找到最后一个起点开始，然后又遍历回来，又饶了一圈，总共两圈。在博客（2）中引入了另一个方法
假如我们从起点开始，假设车开出站点p后，油箱空了，假设sum[1] = diff[0] +diff[1] + ... + diff[p]，可知sum[1] < 0；接着以p+1节点为起点往下走，以此类推，油箱依次为sum[2],sum[3],...sum[m]。sum[m]为走到最后一个车站所剩油量。
如果sum[m]也小于零，则整个diff数组求和肯定小于零。而且走不到终点。（参考【3】）
如果sum[m]大于0，则需要看sum[m]+sum[1]+sum[2]+...+sum[m-1]是否大于等于0，因为sum[1]到sum[m-1]这些序列每个序列除了末尾的点，我们都已经知道是否能够开到最后了，所以只需要把末尾点所需的油量补齐，看看是否为非负。而sum[m]+sum[1]+...+sum[m-1]就是整个duff数组的和。这个思路就可以写出时间复杂度就是O(n)的代码：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int remaining = 0, total = 0;
int startIndex = 0;
int size = gas.size();
for (int stationIndex = 0; stationIndex < size; stationIndex++) {
int diff = gas.at(stationIndex) - cost.at(stationIndex);
remaining += diff; total += diff;
if (remaining < 0) {
if (diff < 0) {
startIndex = stationIndex + 1;
remaining = 0;
} else {
startIndex = stationIndex;
remaining = diff;
}
}
}
return total < 0 ? -1 : startIndex;
}
};
另外，（2）中还提到最大连续子序列。一开始没明白，环形的数据怎么用最大连续子序列来求？后来忽然发现，把环形展开，重复两次，然后求最大子序列，这个意思。后面有空学习下最大子序列算法。
---分割线 2019.02.23---
假设r数组为r:[5,-3,9,-6,-10,2,4] （r数组为用gas数组减去cost数组得到的“净油量”）
（换个方式向写比较容易看得清:
）
从r[0]出发，能否到达r[1]？0+r[0]=0+5=5>0，所以可以到达r[1]，当前油量为5
能否到达r[2]？5+r[1]=5+(-3)=2>0，所以可以到达r[2]，当前油量为2
能否到达r[3]？2+r[2]=2+9=11>0，所以可以到达r[3]，当前油量为11
能否到达r[4]？11+r[3]=11+(-6)=5>0，所以可以到达r[4]，当前油量为5
能否到达r[5]？5+r[4]=5+(-10)=-5，所以不可以到达，还需要油量为5，也就是净油量为-5
那么从r[6]出发，能否到达r[4]？肯定可以，因为r[6]>0，且从r[0]出发本来就可以到达r[4]
能否到达r[5]？r[6]+(-5)=4-5=-1<0，所以不能到达r[4]
同理，从r[5]出发，肯定能到达r[4]（r[5]>0，且r[6]能够到达r[4]）
能否到达r[5]？r[5]+(-1)=2-1=1>0，所以可以到达r[5]。因此从r[5]出发能够完成任务！
但是目前还是不太明白：
1、O(n)算法的原理（非O(2n))
2、怎么证明如果r[0]+r[1]+...+r[n]>0，则存在可以绕一圈的路径
