LeetCode 134：加油站環路問題

題目：環形路線上有 n 個加油站，第 i 站汽油 gas[i]，去下一站耗油 cost[i]。車初始油箱為空，求能否從某站出發繞行一圈，返回起始站索引；不能則返回 -1。

核心洞察

1. 總油量判斷：若 sum(gas) < sum(cost) 則無解，直接返回 -1。若 sum(gas) >= sum(cost)，必存在解。
2. 貪心單程掃描：從 0 站出發累加 tank += gas[i] - cost[i]。若在站 k 發現 tank < 0，則 起點不可能在 [0, k] 之間（因為任何前綴段油量均 ≥ 0，去掉只會更差）。直接將起點候選設為 k+1，tank 歸零繼續。最終候選即為答案。

C++ 實現（貪心 O(n)）

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.size(); ++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²)：從每個非負差值站嘗試，超時。

總結

貪心單程掃描是最優雅解法：利用「總和非負必有解」及「前綴段不可作為起點」兩大性質，一次遍歷即得答案。體現局部最優推導全局最優的貪心精髓。