leetcode题解-134. Gas Station_正圆轨道上有n个加油站

题目：环形路线上有N个加油站，每个加油站有汽油gas[i]，从每个加油站到下一站消耗汽油cost[i]，问从哪个加油站出发能够回到起始点，如果都不能则返回-1（注意，解是唯一的）。

题目分析：暴力的方法比较容易想到，就是从每一个站开始，一直走一圈，累加过程中的净余的油量，看它是不是有出现负的，如果有则失败，从下一个站开始重新再走一圈；如果没有负的出现，则这个站可以作为起始点，成功。时间复杂度是O(n^2)。代码比较直接，这里就不列举了。

我们模拟一下过程：

a. 最开始，站点0是始发站，假设车开出站点p后，油箱空了，假设sum1 = diff[0] +diff[1] + … + diff[p]，可知sum1 < 0；

b. 将p+1作为始发站，开出q站后，油箱又空了，设sum2 = diff[p+1] +diff[p+2] + … + diff[q]，可知sum2 < 0。

c. 将q+1作为始发站，假设一直开到了未循环的最末站，油箱没见底儿，设sum3 = diff[q+1] +diff[q+2] + … + diff[size-1]，可知sum3 >= 0。

要想知道车能否开回 q 站，其实就是在sum3 的基础上，依次加上 diff[0] 到 diff[q]，看看sum3在这个过程中是否会小于0。但是我们之前已经知道 diff[0] 到 diff[p-1] 这段路，油箱能一直保持非负，因此我们只要算算sum3 + sum1是否 <0，就知道能不能开到 p+1站了。如果能从p+1站开出，只要算算sum3 + sum1 + sum2 是否 < 0，就知都能不能开回q站了。

因为 sum1, sum2 都 < 0，因此如果 sum3 + sum1 + sum2 >=0 那么 sum3 + sum1 必然 >= 0，也就是说，只要sum3 + sum1 + sum2 >=0，车必然能开回q站。而sum3 + sum1 + sum2 其实就是 diff数组的总和 Total，遍历完所有元素已经算出来了。因此 Total 能否 >= 0，就是是否存在这样的站点的 充分必要条件。时间复杂度 O(n)。

因此，代码可以简化为：

class Solution {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int start = 0;
        int curGas = 0;
        int sum= 0;
        for(int i = 0; i < len; i++){
            curGas += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if(curGas < 0){  //之前的油量不够到达当前加油站 
                start = i + 1;  
                curGas = 0;
            }
        }
        if(sum < 0){  //所有加油站的油量都不够整个路程的消耗  
            return -1;
        }else{
            return start;
        }
    }
    public static void main(String[] args) {
        int[] gas = {4};
        int[] cost = {5};
        System.out.println(canCompleteCircuit(gas, cost));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26