134. 加油站

推薦事前閱讀：滑動窗口

思路

題目要找到滿足條件的初始點，讓車子能跑一圈加油站，回到最初的起點。
每次前往 $i$ 號加油站的時候，都會消耗 $cost[i]$ 的油量，抵達加油站的時候，則會補充 $gas[i]$ 的油量。
如果有答案存在，題目確保它是唯一的。
假如不用滑動窗口，可以寫出如下 $O(n^2)$ 的程式碼。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for(int i = 0; i < n; i++) { // 窮舉從每一個 i 出發
            int curGas = 0; // 統一在迴圈內加氣，初始設為 0
            bool isOk = true;
            for(int step = 0; step < n; step++) { // 試著走 n 步
                int curr = (i + step) % n; // 當前所在的車站
                curGas += gas[curr]; // 抵達車站，加氣
                if(curGas >= cost[curr]) {
                    curGas -= cost[curr]; // 油量足夠，扣掉前往下一站的油耗
                } else {
                    isOk = false; // 油不夠開到下一站，這個起點失敗
                    break;
                }
            }
            if(isOk) return i; // 成功繞一圈，回傳 0-indexed 的起點
        }
        return -1;
    }
};

接下來就要試著去優化了。我們能將gas跟cost數組相減，得到一個「盈餘」數組gain，
它代表的意思是「從這個點往下個點前進」對應的油量的變動是多少。
此時選擇從一個點 $i$ 出發，它往下個點走的時候，油量變動是 $gain[i]$ ，
假如變動之後來到負數，說明無法前進到這裡，油量不夠。

那要怎麼用滑動窗口的思路去優化呢？
假如現在盈餘數組是 $[3,5,-10,6,7,-4]$ ，從第一個數字 $3$ 開始，往後不斷的累加，
一直到 $-10$ 發現油量小於 $0$ ，也就代表以它為起點是無法正常走一圈的。
現在，我們沒必要從 $5$ 繼續驗證，因為連 $[3,5,-10]$ 都無法正常走一圈，
那麼 $[5,-10]$ 又怎麼可能會通過？因此，新的起點可以從 $-10$ 後面的位置繼續，因為一旦到負數，就會判定不通過。
※累加的起點不可能為負數，也就不可能出現把起點往後挪，卻可以通過的情況存在。

最後，還能用貪心去解決這個問題，
假如整體前綴和 $\geq0$，那麼就一定存在一個起點，能夠環繞一整圈。
詳情見靈茶題解

程式碼

1. 滑動窗口

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for(int i = 0; i < n; i++) gas[i] -= cost[i]; // 直接拿 gas 作為盈餘數組
        for(int i = 0, j = 0; i < n; i = j + 1, j++) { // i = j + 1, 新的起點在現在的負數之後
            int curGas = 0;
            while(curGas + gas[j % n] >= 0) {
                if(j - i + 1 == n) {
                    return i;
                }
                curGas += gas[j % n]; 
                j++;
            }
        }
        return -1;
    }
};

2. 貪心

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for(int i = 0; i < n; i++) gas[i] -= cost[i]; // 直接拿 gas 作為盈餘數組
        int curGas = 0, minGas = 0, res = 0;
        for(int i = 0; i < n; i++) {
            curGas += gas[i];
            if(curGas < minGas) {
                minGas = curGas; // 紀錄最低點
                res = i + 1; // 並以它之後的位置做為新的起點
            }
        }
        return curGas < 0 ? -1 : res; // 整體油量 < 0, 那麼是不可能繞完一圈的, 否則就一定可以
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$