134. 加油站

Problem: 134. 加油站

思路

首先能想到的直观做法是，把gas和cost相减，求出一个每到一站的油量变化，然后我们尝试从某个油量变化为正的站开始，如果能走一圈则答案为该油站，否则从下一个正油站继续尝试遍历。

这样做也能以$O(n)$的复杂度完成，但是代码相对难写，而且还需要判断是否能够走完。

进一步考虑我们可以发现，如果把所有相减值求和，求得的结果为负，那么无论怎样都不能走完，显然是返回-1。

那么对于相减值大于等于零的情况呢？

实际上这样是一定可以走完的。我们利用大于零的性质进行以下推导：

假设到i位，当前的总油量变为了负数，由于所有站的相减值总和大于0，我们可以知道在i+1到n - 1中间的和加上当前累计值肯定大于0，因此我们选择下一个相减值大于0的点，从这个点出发，若能走到n-1，则该点即为答案；否则继续寻找下一个点，而这一直保持了之后的和加上当前累计值一定大于0的性质，所以一定可以找到一个满足要求的点。

在这个过程中我们可以发现，我们只需要找到一个点，从这个点开始能走到结尾即可。

复杂度

• 时间复杂度: $O(n)$，n为数组长度。
• 空间复杂度: $O(1)$。

Code

[]

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += gas[i] - cost[i];
        }
        if (total < 0) return -1;
        int i = 0;
        while (i < n) {
            int sum = 0;
            int start = i;
            while (i < n && sum >= 0) {
                sum += gas[i] - cost[i];
                i++;
            }
            if (sum >= 0) return start;
        }
        return -1;
    }
}