134. Gas Station

──────────────────────────────────────────────────────────────────────

134. Gas Station

環形公路上有 n 個加油站，在第 i 站可以加 gas[i] 的油，從第 i 站開到下一站要耗 cost[i]。油箱無限大、一開始是空的。問從哪一站出發可以繞完一圈；沒有就回傳 -1。題目保證有解時解是唯一的。

思路

這個題目如果我們利用窮舉，一定可以找到開始的加油站（每一站都試著繞一圈，$O(n^2)$），但是這樣一定不是最好的方法，因此要花時間去分析題目。

首先，我們可以知道的是題目有說：雖然可能沒有解，但是如果有解一定存在著唯一解。自此我們可以拆開分析成兩個獨立的問題：

1. 到底有沒有解？
2. 如果有，起點在哪裡？

漂亮的地方是這兩件事可以在同一趟掃描裡完成。

一、什麼時候無解

我們可以先分析沒有解的情況。如果我在某個站沒有油了、無法前往下一站，那就一定是無解嗎？我們不可以這樣斷言，因為可能只是我們的出發站比較不好而已 —— 題目要我們找的就是可行的出發站，所以只是無法前往下一站，我們無法斷言就是無解。

因此我們就去想，如果我們每個站都試過了，但是還是無法完成所有的旅途，那代表的就是：不管我怎麼出發，加油站可以提供的油一定小於我所消耗的。那在這種情況下，我是一定不可能找出任何一個解的。

也就是說反過來看，如果加油站的總油量大於或是等於總成本，那就一定可以完成旅程。這一點的說明是：因為只要總和大於成本，如果我在某一個地方接連消耗掉大量成本，那就一定會在這個路線的另外一段接連的加上油，才能讓總成本大於或是等於零。

用一個極端一點的例子來說，如果我有一段旅程每次的消耗大於加油，那就會產生大量赤字，因此在我從赤字開始轉正的那個點開始，就可以確定後面的旅程一定要有大量的加油，我才能補足之前的赤字。

所以第一個問題的答案很乾脆：把所有 gas[i] - cost[i] 加起來，小於 0 就是無解。

二、為什麼可以直接把起點跳到 i + 1

不過如果我的一段旅程中，這樣的極端例子一直出現呢？這樣也是沒問題的，就只是我們要找到的出發站就又會再被往後推。

但「往後推」推到哪裡？直接跳到失敗的下一站，中間全部不用試 —— 這是這題的貪心核心，也是唯一需要證明的一步：怎麼知道中間那些站不會是答案？

嚴格的理由是這樣。假設從 start 出發，走到站 i 時油量第一次變負：

• 對任何 start < j ≤ i，從 start 到 j-1 的累積量必定 ≥ 0 —— 否則我們會更早失敗，i 就不是第一次變負的地方了
• 於是 $\text{sum}(j..i)=\text{sum}(start..i)-\text{sum}(start..j-1)\le \text{sum}(start..i)<0$
• 也就是說，從 j 出發也會在 i 之前（或就在 i）失敗

所以 [start, i] 這整段裡沒有任何一站可以當起點，可以整段跳過。

有了這個引理，起點就只會單向往前推，整趟掃描是 $O(n)$。

因此綜合上面的分析，我們就可以線性的去找出加油站在哪裡。雖然說我們可以知道答案是唯一解，但是我們還是要把所有的加油站造訪完 —— 要確定的是前面我們講過無解的狀態。

解題方向

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        total, start, fuel = 0, 0, 0

        for i in range(n):
            total += gas[i] - cost[i]        # 全域總和：判斷有沒有解
            if fuel + gas[i] - cost[i] < 0:
                start = i + 1                # 這一段整段跳過
                fuel = 0
            else:
                fuel += gas[i] - cost[i]     # 從 start 出發到目前為止的油量
        if total < 0:    
            return -1
        return start

三個變數各司其職，這是這題最漂亮的地方：

變數	管什麼	會不會歸零
total	全域總和 → 回答「有沒有解」	不會，一路累加到底
fuel	從 start 出發到現在的油量 → 判斷這一段行不行	會，每次失敗就歸零
start	目前的候選起點	只會往前推，不會後退

total 原本命名為 sum，那會遮蔽 Python 的內建函式 sum() —— 這一段程式碼沒用到它所以不會出錯，但遮蔽內建名稱在面試是會被提出來的，換個名字沒有成本。

補充

為什麼不用真的模擬繞一圈

看起來這個迴圈只從 0 走到 n-1，並沒有繞回去。但因為：

• total >= 0 已經保證了「總量夠」
• 貪心的引理保證了 start 之前的每一站都不可能是答案

所以只要 start 之後到終點這一段撐得住（迴圈跑完 fuel 沒有再歸零），繞回去補上前面那段一定也撐得住 —— 前面那段的總和 = total 減去後面那段，而 total ≥ 0。這就是不需要真的模擬環形的原因。

和其他貪心題的對照

55. Jump Game 是同一類「一趟掃描 + 維護一個可行範圍」的貪心。共同點是每一步都能安全地丟掉一整段可能性，而不是回頭重試 —— 和 11. Container With Most Water、167. Two Sum II 的對撞指針是同一個家族的想法（都靠一個「丟掉這些不會漏掉答案」的論證）。

fuel 一旦變負就歸零重來的手法，和 53. Maximum Subarray 的 Kadane 演算法是同一個動作。兩題的核心那一行放在一起看：

# 53:  前面那段對我沒幫助就丟掉，從我自己重新開始
curr = max(num, curr + num)

# 134: 這一段撐不住就丟掉，從下一站重新開始
if fuel + gas[i] - cost[i] < 0:
    start = i + 1
    fuel = 0

都是「累積量變成負擔時就歸零重來」。差別只在要記錄什麼：53 要的是過程中出現過的最大值（所以另外用 ans 記著），134 要的是「最後一次重來的位置」（所以用 start 記著）。想通這件事，兩題就變成同一題的兩種輸出。

複雜度

• 時間 $O(n)$ — 一趟掃描，每站常數次計算；不需要回頭重試，也不需要真的繞環
• 空間 $O(1)$ — 只有三個變數

其中 n 是加油站數量。

對照暴力解的 $O(n^2)$（每一站都試著繞一圈），這題省下來的就是那個引理 —— 它讓失敗時可以整段跳過，而不是退回下一站重來。