---
title: "134. Gas Station"
url: "https://laigary.com/interview/coding/134-gas-station"
type: "note"
section: "coding"
date: "2026-07-21"
updated: "2026-07-28"
tags: ["Greedy", "Array"]
---

# 134. Gas Station

[134\. Gas Station](https://leetcode.com/problems/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)$。

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

## 解題方向

```python
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](/interview/coding/55-jump-game) 是同一類「一趟掃描 + 維護一個可行範圍」的貪心。共同點是**每一步都能安全地丟掉一整段可能性**，而不是回頭重試 —— 和 [11. Container With Most Water](/interview/coding/11-container-with-most-water)、[167. Two Sum II](/interview/coding/167-two-sum-ii-input-array-is-sorted) 的對撞指針是同一個家族的想法（都靠一個「丟掉這些不會漏掉答案」的論證）。

`fuel` 一旦變負就歸零重來的手法，和 [53. Maximum Subarray](/interview/coding/53-maximum-subarray) 的 Kadane 演算法**是同一個動作**。兩題的核心那一行放在一起看：

```python
# 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)$**（每一站都試著繞一圈），這題省下來的就是那個引理 —— 它讓失敗時可以整段跳過，而不是退回下一站重來。