134. Gas Station
C++，模拟题大概？？？参考热评大佬，然后说下自己的理解和思路。
有解的话要满足两个条件：
- 所有站点的油量和要大于跑一整圈的耗油量的和
- 绕圈的途中，在任何一个站点加完油后，都要能到达下一个站点
假设起始站点为0，一旦遇到在k站无法到达k+1站的情况，则说明起始站一定不在k及k之前，原因如下（假设油箱中剩余油量为rest）：
- 首先确定一个结论：每成功到达一个站，剩余油量rest一定是>=0的
- 如果在k站无法到达k+1站，根据上述结论，说明以0,1,2,3…k等站为起始站，都不能让车子从k站到达k+1站
- 于是可以确定，起始站一定不在k及k之前，所以假设起始站为k+1站
于是代码如下：
代码如下：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start = 0;
int run = 0;
int rest = 0;
for (int i = 0 ; i < gas.size(); i++) {
run += gas[i] - cost[i];
rest += gas[i] - cost[i];
if (run < 0) {
run = 0;
start = i + 1;
}
}
if (rest >= 0) return start;
else return -1;
}
};
