gas station

There are N gas stations along a circular route, where the amount of gas at station i isgas[i]. You have a car with an unlimited gas tank and it costscost[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.

解析

定义一个全局的剩余油量total，定义一个 记录i到i+1是否可行（即加上在本加油站加油的数量-本加油站到下一加油站加油之前消耗的油量），定义一个站点的索引值index。我们注意到，如果sum<0，也就是说从第i到第i+1个点不可行，那肯定我们原先定义的那个index的位置是无法能够转完一圈的（因为在第i点和第i+1点这里断了）。我们就令sum=0，然后令index=i，相当于说从i+1个点开始了（所以在下面return的时候是Index+1），然后开始继续往下走，如果i还没有走到最后一个，sum又小于0了，那么与前面一样，肯定要从下一个点开始，假定为起点。当一直到最后一个sum都没有小于0的话，且total也大于等于0的话，那么自然从i+1开始往后到最后一个点，再从最后一个点到起点一直到i，再到i+1是可以构成一个圈。若total<0的话，则铁定i到i+1所用的油量无法用total补充回来，因此还是断开的，所以无法完成一圈，故返回-1。

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int total=0;
    int sum=0;
    int index=-1;
    for(int i=0;i<gas.size();i++)
    {
        sum+=gas[i]-cost[i];
        total+=gas[i]-cost[i];
        if(sum<0)
        {
            sum=0;
            index=i;
        }
    }
    return (total>=0)?index+1:-1;
    
}