[LeetCode] 134. 加油站

时间：2020-06-17 13:53:43 收藏：0 阅读：48

看了官方解答的答案，不用从后面的节点倒回来更新值，直接用一个total值来存储整个的值

如果total》=0，说明能形成环路，否则错误。

注意其中的证明。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total=0;
        int cur=0;
        int n=gas.length;
        int startIndex=0;
        for(int i=0;i<n;i++){
            total +=gas[i]-cost[i];
            cur +=gas[i]-cost[i];

            if(cur<0){
                startIndex=ai+1;
                cur=0;
            }
        }
        return total>=0?startIndex:-1;
    }
}

原文：https://www.cnblogs.com/doyi111/p/13152038.html