此题可以参照acwing1088旅行问题可以用单调队列做，但是空间复杂度是O(N)的

贪心

暴力的思想：

• 枚举每个起点
• 对于每个起点来说，枚举是否可以走完一圈

暴力的 $时间复杂度O(N^2)$

贪心优化：

结论:如果x最远能到y点，y + 1点到不了，那么从x到y的任一点k出发都不可能到达y+1。

证明:
因为从k点出发的话，相当于从0开始加油，而如果从x出发到k点的油量一定是>=0的，即有还有剩余的油。既然不从0开始都到不了y+1，那么从0开始就更不可能到达y+1了。

综上：

• 枚举起点i

• 对于每个起点，枚举最远能到的点y，下次枚举从y + 1点作为起点枚举

$ 时间复杂度O(N),空间复杂度O(1)$

参考文献

lc究极班

AC代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        //枚举起点
        for (int i = 0, j ; i < n ; ){
            int now = 0;
            //枚举i点能跳j步
            for (j = 0 ; j < n ; j ++){
                now += gas[(i + j) % n] - cost[(i + j) % n];
                if (now < 0) break;
            }
            if (j == n) return i;//当前i点能够走完
            i = i + j + 1 ;//跳到y + 1点
        }
        return -1;

    }
};