解題說明
Gas Station（加油站）
題目描述：環形路上有 n 個加油站，第 i 站可加油 gas[i] 升，從第 i 站開到第 i+1 站耗油 cost[i] 升。油箱容量無上限，初始油量為 0。若存在起始加油站使得汽車能環繞一圈，請輸出該站的索引；否則返回 -1。題目保證答案唯一。
解題思路：
關鍵定理：若所有站的總油量 sum(gas) >= sum(cost)，則解一定存在。
貪心找起始點：
- 維護
tank（從start出發到當前站的累計剩餘油量） - 逐站計算
tank += gas[i] - cost[i] - 若
tank < 0：說明從start到 i 都無法作為起點（任何中間站出發只會有更少的油，因為少了前段的補給），將start重設為i+1，tank歸零 - 最終若
total >= 0，返回start；否則返回 -1
正確性說明：
- 若從 A 出發，到 B 時
tank < 0，則 A 到 B 之間任意一站 C 為起點時，到達 B 時的油量 = （從 C 出發的油量）- （A 到 C 段的正貢獻）≤ 從 A 出發到 B 的油量 < 0。因此 A 到 B 之間沒有有效起點。 - 當總量 ≥ 0 時，最後確定的
start（即剩餘段的起點）一定能繞完整圈，因為前半段的「虧欠」會由後半段的「盈餘」補回。
C++ 解法
複雜度分析
時間複雜度：O(n) — 只需對所有加油站進行一次線性掃描，每站 O(1) 更新。
空間複雜度：O(1) — 只使用常數個輔助變數（total、tank、start），不需要額外陣列或資料結構。
虛擬碼
1. Initialize total=0, tank=0, start=0
2. For each station i from 0 to n-1:
a. diff = gas[i] - cost[i]
b. total += diff
c. tank += diff
d. If tank < 0:
- start = i + 1 (stations [old_start..i] are all invalid starts)
- tank = 0 (reset surplus for new candidate)
3. If total >= 0: return start (solution guaranteed to exist)
Else: return -1 (impossible to complete circuit)其他解法
暴力模擬 O(n²)：對每個站 i 嘗試作為起點，模擬一圈行駛過程，若全程油量始終非負則返回 i。最壞情況需嘗試 n 個起點，每次模擬 O(n)，總計 O(n²)。邏輯直觀但效率不足，n 較大時會超時。
前綴和 + 最小值定位 O(n)：計算 prefix[i] = sum(gas[0..i] - cost[0..i])，起點應選使得全程前綴和始終 ≥ 0 的位置，等同於找前綴和序列的最小值點之後一位。數學推導嚴謹，但實作較貪心版繁瑣，兩者時間複雜度相同。
延伸思考
- 若題目不保證答案唯一，且需要返回所有可能的起始站，應如何修改演算法？
- 若油箱有最大容量限制（無法攜帶超過 C 升油），問題的解法是否仍然可行，需要哪些調整？
- 本題的貪心正確性依賴「總量 ≥ 0 時解必存在」的定理，能否用反證法嚴格證明此定理？