LeetCode 134 Gas Station：環形加油站問題的貪心解法

問題描述

有 N 個加油站環形分布，第 i 站有汽油 gas[i]，開往下一站消耗 cost[i]。車油箱無限大，起始油量為 0。求能否繞行一圈，若能返回起始站索引，否則返回 -1。保證解唯一。

核心洞察

總油量 ≥ 總消耗 ⇔ 存在解。若總和 sum(gas[i] - cost[i]) < 0，無論從哪裡出發都無法完成。若總和 ≥ 0，則必存在唯一起點。

進一步觀察：若從站 s 出發，在站 k 時油量變負，則 s 到 k 之間的任意站都不能作為起點（因為從 s 到該站油量非負，若從中間出發油量只會更少）。因此可以直接跳過這些站，從 k+1 繼續嘗試。

貪心算法流程

1. 初始化 total = 0（總盈虧）、tank = 0（當前油量）、start = 0（候選起點）。
2. 遍歷 i = 0..N-1：
    diff = gas[i] - cost[i]
 total += diff; tank += diff;
    若 tank < 0：start = i + 1; tank = 0;
3. 遍歷結束，若 total >= 0 返回 start，否則返回 -1。

Java 參考實現

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; ++i) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

複雜度分析

• 時間：O(N) — 單次遍歷。
• 空間：O(1) — 只用常數額外變量。

總結

Gas Station 是貪心算法的經典案例：利用「區間和為負則區間內無可行起點」的性質，線性掃描即可找到唯一解。關鍵在於證明總和非負時解必存在且唯一，以及跳過策略的正確性。