134. Gas Station 加油问题
134. Gas Station 加油问题
每个油站有汽油值和到下一个站需要的汽油值，问：从哪个下标的油站开始走（初始汽油为0）能够走完所有的油站，走不到返回 -1
隐含条件：
- 所有油站的汽油值和必须大于所有 cost 之和
- 如果从某起点到某终点走不到，那么其中的任何一个站出发都不可能到，写几个式子可以简单证明
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total=0, sum=0, start=0;
for(int i=0;i<gas.size();++i) {
total += gas[i]-cost[i];
sum += gas[i]-cost[i];
if (sum < 0) {
start = i+1;
sum=0;
}
}
return (total<0) ? -1 : start;
}#greedy