134. Gas Station

题目描述：圆形路径上有 n 个加油站，每个加油站的油量是gas[i]，你的车有一个无限大的油箱，从第 i 个加油站到下一个需耗费cost[i]的油量，开始时你的车以空油箱停在一个加油站，如果能走玩一圈则返回起始油站，否则返回 -1。解是唯一的。

分析：基本思路是分别以每个加油站为起点模拟，时间复杂度O(n^2)。线性O(n)复杂度的算法是设两个变量，一个判断总共的汽油量是否大于总消耗量，一个判断路程中是否会出现油箱中剩油不够到下一站的消耗的情况。

代码：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int all = 0;                //记录总油量与总消耗量的差值
        int j = 0;                  //记录起始点用于返回
        for (int i = 0, s = 0;i < gas.size(); i ++)
        {
            s += gas[i] - cost[i];                   //当前站加的油量和先前的站剩下的油，与到下一站的消耗量的差值
            all += gas[i] - cost[i];
            if ( s < 0)      //不够，说明第 i 站不能作为起始站。若是初始，说明空油箱在第 i 站加满还不能到下一站；若是中途，说明剩油与此站加油量的和不够到下一站，即若以此站及其前站为起点，到此站都会无法前进
            {
                j = i + 1;
                s = 0;
            }
        }
        return all >= 0? j : -1;           //只要最后总油量与总消耗量的差值为正，则从j 到 n 的剩油量一定够前面每站的缺失，即从 j 出发一定能走完
    }
};