LeetCode 134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to 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, otherwise return -1.

Note:
The solution is guaranteed to be unique.
解析：
我们先来将问题做一个转化：将每个站的加油量减去从当前加油站到下一个加油站的代价，即等于当前加油站到下一个加油站净剩余的油量，如果能保证从某个加油站出发到终点的过程中，所有净剩余油量的累加都不小于0，那么该问题有解。
这个问题的两个属性为：
1 如果总的gas – cost小于零的话，那么没有解返回-1。通过设置total变量记录总的油量，一次循环即可完成处理，避免了两层循环。
2 如果前面所有的gas – cost加起来小于零，那么前面所有的点都不能作为出发点。

[cc lang=”C++”]
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int total = 0;//从起点出发到终点剩余的油量
int j = -1;
for(int i=0, sum = 0; i < gas.size(); ++i) { total += gas[i] – cost[i]; sum += gas[i] – cost[i]; if(sum < 0)//油箱空了，需要从下一个节点开始 { j = i; sum = 0; } } return total >=0?j+1:-1;
}
};
[/cc]