liyirui's Blog

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。