题意

一个环上，每经过第i个点，增加A[i]再减少B[i], 要求每个结果不小于零

限制：

环长度不大于$10^{4}10^4$, 增减值不大于$10^{5}10^5$

方法

枚举起点

直接按照题意，枚举所有起点.

对于每次枚举起点，模拟行驶一周，判断是否会出现油量为负的情况。

如果找到能让油量始终非负的起点，输出即可。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    int gasStation(vector<int>& gas, vector<int>& cost) {
        for(int i = 0;i<gas.size();i++){ // 枚举起点
            int cur  = 0;
            bool ok = true;
            for(int j = 0;j<gas.size();j++){ // 走一圈
                int p = (i+j)%gas.size();
                cur+=gas[p] - cost[p]; // 计算当前剩余
                if(cur < 0){ // 剩余小于零
                    ok = false;
                    break;
                }
            }
            if(ok) return i; // 全部合法
        }
        return -1;
    }
};

复杂度分析

时间复杂度: 对于每个起点最坏情况走了几乎整个环，所有时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 只用了常熟个额外变量，所以空间复杂度为$O(1)O(1)$

基于数学的时间复杂度优化

首先如果 花费的和 大于 加油的和，那么一定不可行。因为如果走一圈，刚好是所有加油减去所有花费。

剩下即是 花费的和 小于等于 加油的和 的情况。

先不考虑负值会停止移动，假设负值也能继续移动，那么从任何一点出发，走一圈以后，到达出发点，剩余的油量一定大于等于原油量。

先选定从第一个点出发，记录每个点上油量的剩余，找到剩余油量最小的位置。设置这个位置为新的出发点。

也就是原来如果从A开始绕一圈，其中走到B时，油量剩余最小。现在改为从B触发走一圈，

即是由A->B->A变为B->A->B。

其中B->A的部分，因为新的方案起始油量更大，所以B->A在新的方案中每个位置的油量都比原来大，所有都大于等于零

其中A->B的部分，也因为新的方案中，走到A时，油量比原来大，所以这一段中也比原来的油量大，所以也都大于等于零

以题目中的样例数据[1,2,3,4,5],[3,4,5,1,2]为例

所以输出 下标3

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    int gasStation(vector<int>& gas, vector<int>& cost) {
        int sg = 0;
        int sc = 0;
        for(auto v:gas){ // 所有 gas和
            sg+=v;
        }
        for(auto v:cost){ // 所有 cost和
            sc+=v;
        }
        if(sc > sg) return -1; // gas 不小于cost
        int minv = 0; // 最小值
        int cur  = 0;
        int mini = 0; // 最小值下标
        for(int i = 0;i<gas.size();i++){
            cur += gas[i] - cost[i]; // 当前值
            if(cur < minv){
                minv = cur;
                mini = i;
            }
        }
        return (mini+1)%gas.size();
    }
};

复杂度分析

时间复杂度: 对于每个位置，操作次数为常数，所以时间复杂度为$O(n)O(n)$

空间复杂度: 只用了常熟个额外变量，所以空间复杂度为$O(1)O(1)$