LeetCode Gas Station：環形加油站貪心解法

題目大意

N 個加油站成環，gas[i] 為可加油量，cost[i] 為開往下一站耗油。油箱無限大。求能否環行一圈的起始站索引，不能則 −1。解唯一。

貪心證明

定義 diff[i] = gas[i] − cost[i]。
1. 若 Σ diff < 0 → 總油量不足，無解。
2. 否則必存在解。從 0 開始累加 tank，若在 i 處 tank < 0，則 [start, i] 都不可能是起點（因為任意 k∈[start,i] 起步，到 i 時剩油 ≤ 當前 tank < 0）。
直接將 start 設為 i+1，tank 歸零繼續。最終 start 即為答案。

代碼實現

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
        int n = gas.size(), total = 0, tank = 0, start = 0;
        for (int i = 0; i < n; ++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) 空間。單次遍歷即得答案。