134 Gas Station(Medium)

1.在做pat的to fill or not to fill的时候想起同样是加油站的题目，于是翻出来复习一下
2.关键在于理解潜在的条件。假设油量为tank，如果到了当前站i，tank<0，即不能到达站i+1，那么起始站start和i之间的任何一个站i都不能到达站i+1。因为每个站至少贡献了0或者>0的油量，去掉一个站，那么tank必然比现在的油量还要小，所以更加不可能达到i+1.

证明：
设tank[a,b]是指以a为起始站，到达b站后，油箱的油量。
如果上述2结论不成立，则可以推导出，在start与i之间的某一个站j，使得tank[j,i]>tank[start,i]，又tank[start,i]=tank[start,j]+tank[j,i]，那么推得tank[start,j]<0，
而车能够从start走到i，所以对于任意k属于[start,i]，均有tank[start,k]>=0，与tank[start,j]<0矛盾，所以2结论是正确的。

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.

AC代码：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tank=0;//当前的油箱油量
        int start=0;//从第0个站开始计算，后面也作为结果进行返回
        int n=gas.size();
        for(int i=0;i<gas.size();i++)
        {//遍历所有加油站
            tank+=gas[(i+start)%n]-cost[(i+start)%n];//更新油箱的油量
            if(tank<0)
            {//如果tank小于0，表明没办法从i走到下一个油站,那么start直接从下一站开始
            //如果无法从start达到i，那么start和i之间任何一个站都不能达到i，因为每个站至少贡献了0和>=0的油量
                start=i+start+1;//start从当前i站的下一个站开始
                i=-1;//使得下次从i=0开始
                if(start>=n)
                {//已经把所有情况都遍历了，仍不能满足要求
                    return -1;
                }
                tank=0;
            }
        }
        return start;
    }
};