Leetcode-134. 加油站

本题最容易想到的方法就是将每一个站点都作为起点，逐一尝试是否能从该点绕行一圈。

通过官方题解可以知道，这里还存在可以优化的点。

我们假设从x可以到达y之前的所有的地点，但是无法到达y，那么很容易理解，x与y之间任意的一点 i 都无法到达y，否则就可以先从x到达i再从i到达y。

所以，从x开始遍历，当发现无法到达y时，就说明无法从x实现绕行一圈的目标，根据之前得到的认识，我们也没办法从x与y之间的点到达y，所以这些点也就被排除掉了，之后从y重新开始遍历。

最后只需要遍历一遍，所以总的时间复杂度为O(N)。

代码写法如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
        int len = gas.size();
        for(int i = 0; i < len; ){
            int oil = 0;
            bool flag = true;
            for(int j = 0; j < len; j++){
                int k = (i+j) % len;
                int d = oil + gas[k] - cost[k];
                if(d < 0){
                    i = i + j + 1;
                    flag = false;
                    break;
                }
                else oil = d;
            }
            if(flag) return i;
        }
        return -1;
    }
};

优化的核心就是一句话，从x可以到达y之前的所有的地点，但是无法到达y，x与y之间任意的一点 i 都无法到达y。