这题的证明挺有意思的,可以看一下官方题解。
从某一个车站出发,只要到最后一个车站的油够用,并且全程的油耗加起来大于等于0,那么从该车站出发就能走一圈。
C++代码:
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int res = 0;
int sum = 0;
int cur_tank = 0;
for(int i = 0; i < gas.size(); i++){
sum += (gas[i] - cost[i]);
cur_tank += (gas[i] - cost[i]);
if(cur_tank < 0){
cur_tank = 0;
res = i + 1;
}
}
if(sum < 0 || res == gas.size()) return -1;
return res;
}
};