LeetCode 134：加油站——環形路線能否跑完全程的貪心判斷

題目描述

n 個加油站成環，第 i 站汽油 gas[i]，到下一站耗油 cost[i]。車油箱無限大，起始油為 0。求能跑完全程的起始站索引，否則 -1。解唯一。

貪心證明

• 若總油量 ∑gas < ∑cost，不可能跑完全程 → 返回 -1。
• 否則必存在解。遍歷維護 currTank（當前油量），若 currTank < 0，說明從當前起始站到此站不可行，將起始站設為 i+1，重置 currTank=0。
• 最終剩餘的起始站即為答案。

C++ 代碼

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, curr = 0, start = 0;
        for (int i = 0; i < gas.size(); ++i) {
            int diff = gas[i] - cost[i];
            total += diff;
            curr += diff;
            if (curr < 0) {
                start = i + 1;
                curr = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
};

關鍵點

• 一次遍歷同時完成總和判斷與起始站搜索。
• 證明核心：若區間 [start, i] 不可行，則區間內任意站作為起點也不可行（因為前綴和非負）。

複雜度

• 時間：O(n)。
• 空間：O(1)。