134. Gas Station

題目 / Problem

中文： 有 n 個加油站排成一個環形路線，第 i 個加油站有 gas[i] 單位的汽油。你開著一輛油箱無限大的車子，從第 i 個加油站開到下一個 (i+1) 個加油站需要花費 cost[i] 單位的汽油。你從某一個加油站出發，初始油箱是空的。

給定兩個整數陣列 gas 和 cost，如果你能順時針繞行一圈，回傳起始加油站的索引；否則回傳 -1。如果有解，保證解是唯一的。

English: There are n gas stations on a circular route. Station i has gas[i] units of gas, and traveling from station i to station i+1 costs cost[i] units. You start with an empty tank at one station. Return the starting station's index if you can complete one full clockwise loop, otherwise return -1. If a solution exists, it is guaranteed to be unique.

Constraints: - n == gas.length == cost.length - 1 <= n <= 10^5 - 0 <= gas[i], cost[i] <= 10^4

Example 1:

Input:  gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3

從索引 3 出發：tank = 4 → 8 → 7 → 6 → 5，剛好繞回索引 3。 Starting at index 3: the tank evolves 4 → 8 → 7 → 6 → 5, which is exactly enough to loop back.

名詞解釋 / Glossary

• Greedy algorithm / 貪心演算法：每一步都做當下看起來最好的選擇，不回頭重算。本題利用「若從 A 走不到 B，則 A 與 B 之間的任何站都不能當起點」這個觀察來跳過大量無效起點。 At each step, take the locally best option without backtracking. Here we use the fact that if A can't reach B, no station between A and B can either, letting us skip many invalid starts.

• Circular array / 環形陣列：陣列尾端會接回頭部的索引方式，常用 i % n 來模擬。本題的路線就是環形的。 An array where index n wraps back to 0, often simulated with i % n. The route in this problem is circular.

• Prefix sum (running total) / 前綴和（累計值）：一邊走一邊累計 gas[i] - cost[i] 的和；任何時刻油量為負，表示這段起點不可行。 Keep a running sum of gas[i] - cost[i]. Whenever it dips below zero, the segment we tried to start from is infeasible.

• Invariant / 不變量：演算法執行過程中始終為真的性質。本題的關鍵不變量是：「若 total >= 0，解一定存在；且最後一個讓累計油量歸零的位置之後的下一站，就是答案」。 A property that always holds during execution. Key invariant: if total >= 0 a solution must exist, and the station after the last "tank-reset" point is that answer.

• int overflow / 整數溢位：兩個 int 相加超出範圍會繞回成負數。n 最多 10^5 而 gas[i] 最多 10^4，總和最多 10^9，仍在 32-bit int 範圍內，所以本題用 int 安全。 Adding two ints past the 32-bit limit silently wraps. Here the worst-case sum is ~10^9, still inside int's range, so plain int is safe.

思路

中文： 最直觀的暴力解是：對每個起點 i，模擬從 i 開始繞一圈是否油量永遠非負。每次模擬最多走 n 步，總共 n 個起點，時間複雜度 O(n^2)，當 n = 10^5 時太慢。

我們先觀察一個關鍵事實：把所有 gas[i] - cost[i] 加總，這個總和如果是負的，代表整圈油不夠用，無論從哪裡出發都不可能繞完，直接回傳 -1。反之，如果總和 >= 0，保證存在一個合法起點（題目也保證解唯一）。

接著是貪心的核心觀察：假設我們從站 s 出發，一路累計油量 tank，走到站 j 時 tank 第一次變成負數。那麼「從 s 到 j 之間的任何一個站」都不可能是合法起點——因為從中間某站 k 出發，等於丟掉了 s..k-1 那段（而那段累計是非負的，丟掉只會更糟），所以走到 j 一樣會失敗。結論：下一個可能的起點是 j+1，把 tank 歸零從 j+1 重新開始。

整個演算法只需一次線性掃描，維護兩個累計值：total（整圈總和，用來判斷有無解）和 tank（目前嘗試這段的累計值，一旦變負就重設起點）。

English: The brute-force approach is to try every station as a start and simulate a full loop, costing O(n^2). With n up to 10^5 this is too slow.

First observation: summing all gas[i] - cost[i] tells us whether the trip is even feasible. If the total is negative, we lose more gas than we gain over one loop, so no start works — return -1. If the total is non-negative, a valid start is guaranteed to exist.

Now the greedy insight: suppose we start at station s and the running tank first goes negative at station j. Then no station between s and j can be a valid start either — picking some later station k in that range means dropping the segment s..k-1 whose contribution was non-negative, which can only hurt. So we jump straight to j+1 as the next candidate start, reset the running tank to 0, and continue.

This gives a single linear pass that tracks two sums: total (the full-loop balance, telling us whether any answer exists) and tank (the running balance of the current candidate segment, which resets whenever it drops below zero).

逐步走查 / Walkthrough

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Per-station diff gas[i] - cost[i]: [-2,-2,-2,3,3]

End of loop: total = 0 >= 0, so a solution exists, and the last candidate is start = 3. Return 3.

注意 / Note: 我們不必真的再從索引 3 走一圈驗證——只要 total >= 0 配合貪心更新規則，最後留下的 start 就是唯一合法答案。 We don't need to re-simulate from index 3; once total >= 0 and the greedy reset rule has been applied, the surviving start is provably the unique valid answer.

Solution — C

// 演算法 / Algorithm:
// 一次線性掃描，維護 total（全程淨油量）與 tank（目前候選段的淨油量）。
// 每當 tank 變負，代表此段任何站都不能當起點，把起點重設為下一站、tank 歸零。
// 結束後若 total < 0 回傳 -1，否則回傳最後保留的起點。
// One linear pass tracks `total` (full-loop balance) and `tank` (current
// segment balance). Whenever `tank` goes negative, no station in the current
// segment can be a valid start, so we move start to i+1 and reset tank.

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    // gasSize 與 costSize 題目保證相等，這裡用 gasSize 即可。
    // gasSize == costSize is guaranteed; we only need one of them as n.
    int n = gasSize;

    int total = 0;   // 全程 gas[i]-cost[i] 的總和 / running sum over the entire loop
    int tank  = 0;   // 目前候選段的累計油量 / running tank for the current candidate segment
    int start = 0;   // 目前候選的起始站索引 / index of the current candidate start station

    // 走訪每一個加油站一次 / visit every station exactly once
    for (int i = 0; i < n; i++) {
        // 這一站淨增加的油量；可能為負（cost 大於 gas）/
        // net gas change at station i; can be negative when cost > gas
        int diff = gas[i] - cost[i];

        total += diff;   // 加進整圈總和 / accumulate into the full-loop balance
        tank  += diff;   // 加進此段的油量 / accumulate into this segment's tank

        // 若油量變負，說明從 start 到 i 中的任一站都不能當起點 /
        // If tank went negative, no station from `start` to `i` can be a valid start.
        if (tank < 0) {
            start = i + 1;  // 下一個可能起點是 i+1 / next candidate start is i+1
            tank  = 0;      // 重置此段的累計 / reset segment tank to 0
        }
    }

    // total >= 0 才存在合法起點；否則整圈油不夠用 /
    // A valid start exists iff total >= 0; otherwise the loop is infeasible.
    // 三元運算子 ? : 等同於 if-else 的精簡寫法 /
    // The ternary `cond ? a : b` is shorthand for an if-else expression.
    return total >= 0 ? start : -1;
}

Solution — C++

// 演算法 / Algorithm:
// 同 C 版本：單次線性掃描，total 判斷可行性，tank 變負就重設起點。
// 若 total < 0 回傳 -1，否則回傳最後留下的 start。
// Same as the C version: a single linear pass, where `total` decides
// feasibility and `tank` going negative triggers a start reset.

class Solution {
public:
    // vector<int> 是 STL 的動態陣列；用 const& 傳入避免複製 /
    // vector<int> is the STL dynamic array; pass by const& to avoid copying.
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // .size() 回傳的是 size_t（無號），轉成 int 比較直觀且避免無號比較陷阱 /
        // .size() returns size_t (unsigned); cast to int for clearer signed loops.
        int n = static_cast<int>(gas.size());

        int total = 0;   // 全程淨油量總和 / full-loop net balance
        int tank  = 0;   // 目前候選段的累計 / current segment's tank
        int start = 0;   // 目前候選起點 / current candidate start

        // 範圍式 for 也可，但用索引版本更貼近題意（需要記 i+1 當下一起點）/
        // A range-for would work, but indexed loop fits naturally since we need i+1 on reset.
        for (int i = 0; i < n; ++i) {
            int diff = gas[i] - cost[i];   // 此站淨增油量 / net change at station i
            total += diff;                 // 累計入整圈總和 / add to full-loop sum
            tank  += diff;                 // 累計入目前段 / add to current segment

            // 油量轉負 → 跳過 [start..i]，從 i+1 重啟 /
            // tank dipped below zero → skip [start..i], restart at i+1
            if (tank < 0) {
                start = i + 1;
                tank  = 0;
            }
        }

        // C++ 同 C：用三元運算子簡潔表達 / ternary picks the answer concisely
        return total >= 0 ? start : -1;
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只用一個 for 迴圈走訪每個加油站一次，每步做常數時間的加法與比較。n 是加油站數量。 We visit each station once with constant-time work per step. n is the number of stations.

• Space: O(1) — 只用了 total、tank、start、diff、n 這幾個整數變數，與輸入大小無關。 Only a handful of integer variables are used, independent of input size.

Pitfalls & Edge Cases

• 誤以為要真的模擬一圈驗證 / Thinking you must re-simulate from start to verify： 一旦 total >= 0，貪心保留下來的 start 就是答案，不需再走一圈。這正是把 O(n^2) 降到 O(n) 的關鍵。 Once total >= 0, the greedy start is provably correct; re-simulating wastes time and is what differentiates O(n) from O(n^2).

• 重設後忘了把 tank 歸零 / Forgetting to reset tank after moving start： 如果只更新 start = i+1 而沒有 tank = 0，下一段的判斷會被前段的負值汙染，完全錯誤。 Updating start without zeroing tank lets the previous segment's negative balance bleed into the next one — the algorithm breaks.

• 回傳 start 而沒先檢查 total / Returning start without checking total first： 例如 gas=[2,3,4], cost=[3,4,3]，total = -1，最後 start 會停在 2，但答案其實是 -1。total 檢查是不可省的。 E.g. gas=[2,3,4], cost=[3,4,3] ends with start = 2 but the correct answer is -1. The total check is mandatory.

• 環形繞回的起點越界 / Start going past n on the final reset： 若最後一站讓 tank 變負，start 會被設成 n。但此時 total 必為負（整圈最後一筆是負，前段又被丟過），會走 -1 分支，所以不會真的拿越界的 start 當答案。 If the very last station triggers a reset, start becomes n. But total is necessarily negative in that case, so the -1 branch fires and we never return the out-of-range index.

• int 是否會溢位 / Whether int can overflow： 最壞情況 n * max(gas[i]) = 10^5 * 10^4 = 10^9，仍在 32-bit int（約 2.1×10^9）範圍內，可放心用 int。若題目放大十倍就要改用 long long。 Worst-case sum is about 10^9, well within 32-bit int. If constraints were 10× larger, switch to long long.