題目

在一條環(huán)路上有 N 個加油站，其中第 i 個加油站有汽油 gas[i] 升。

你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從其中的一個加油站出發(fā)，開始時油箱為空。

如果你可以繞環(huán)路行駛一周，則返回出發(fā)時加油站的編號，否則返回 -1。

說明:

• 如果題目有解，該答案即為唯一答案。
• 輸入數(shù)組均為非空數(shù)組，且長度相同。
• 輸入數(shù)組中的元素均為非負數(shù)。

題目鏈接：https://leetcode-cn.com/problems/gas-station

樣例

樣例1

輸入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

輸出: 3

解釋:
從 3 號加油站(索引為 3 處)出發(fā)，可獲得 4 升汽油。此時油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站，此時油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站，此時油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站，此時油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站，此時油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號加油站。
因此，3 可為起始索引。

樣例2

輸入:
gas = [2,3,4]
cost = [3,4,3]

輸出: -1

解釋:
你不能從 0 號或 1 號加油站出發(fā)，因為沒有足夠的汽油可以讓你行駛到下一個加油站。
我們從 2 號加油站出發(fā)，可以獲得 4 升汽油。 此時油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站，此時油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站，此時油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站，因為返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，無論怎樣，你都不可能繞環(huán)路行駛一周。

解題思路

（1）暴力法

使用暴力是可以過，題目說只有唯一答案，我們就可以對每一個加油站進行遍歷。如果該加油站能夠順利的走完一遍所有加油站的話，那么該加油站就是唯一的一個答案。但是時間復雜度太高了，極端情況下需要對我們的站進行雙重遍歷，即O(n²)的復雜度。參考代碼如下：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //思路：可以for循環(huán)對每個加油站進行一次完整的模擬
        //時間復雜度大概為n^2，這是下策
        //具體實現(xiàn)思路，先對我們的gas和cost進行復制，保證我們可以進行一次循環(huán)，即gas.length循環(huán)
        int[] doubleGas = new int[gas.length * 2];
        int[] doubleCost = new int[cost.length * 2];
        
        for(int i = 0; i < doubleGas.length; i++){
            doubleGas[i] = gas[i % gas.length];
            doubleCost[i] = cost[i % cost.length];
        }
        int res = -1;
        for(int i = 0; i < gas.length; i++){
            //只能從這里面每一個站進行出發(fā)
            int need = 0; //開到下一個站所需要的汽油，身在初始站，所以需要為0
            for(int j = i; j < i + gas.length; j++){
                //對后面站進行加油并減去去下一個站的油，如果遇到油不夠的，則立即停止從那么再重新選一個出發(fā)點
                need += doubleGas[j];
                need -= doubleCost[j];
                if(need < 0) break;
                //如果剛好可以走完一個for循環(huán)，題目有唯一解，這就是答案
                if(j == (i + gas.length - 1)) res = i;
            }
        }
        return res;
    }
}

（2）貪心。上面的代碼總的來說，看起來實在丑陋。不僅用了額外的空間，而且時間復雜還巨高。所以我們需要用貪心來寫這一題。其實就是暴力的原理然后進行一定的優(yōu)化，需要我們?nèi)グl(fā)現(xiàn)一定的優(yōu)化規(guī)律。

我們先來看一個例子，如下。

同樣的，我們的加油站也是這樣的。如果一個加油站循環(huán)一周，也就是到達自己的位置，那么我們可以直接從它可以到達的最遠位置的下一個位置作為出發(fā)點。如果找到可以循環(huán)一周的點的話，那么這個點就是我們的唯一答案出發(fā)點。下面是參考代碼：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int j = i;
            int res = gas[i];
            while (res - cost[j] >= 0) {  //汽油足夠消耗
                //減去我們消耗的，并加上下一個加油站給的油
                res += gas[(j + 1) % n] - cost[j];
                j = (j + 1) % n;
                //如果可以循環(huán)一周的話，說明這就是唯一答案
                if (j == i) return i;
            }
            //最遠距離繞到了i之前，所以 i 后邊的點出發(fā)（i - n）都不可能繞一圈了,并且i之前肯定都是遍歷過的，所以直接無解。
            if (j < i) return -1;
            //i還是小于j（i <= j < n），i 直接跳到 j，外層 for 循環(huán)執(zhí)行 i++，相當于從 j + 1 開始考慮
            i = j;
        }
        //找不到唯一答案
        return -1;
    }
}