題目描述:環形路上有 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正確性說明:
tank < 0,則 A 到 B 之間任意一站 C 為起點時,到達 B 時的油量 = (從 C 出發的油量)- (A 到 C 段的正貢獻)≤ 從 A 出發到 B 的油量 < 0。因此 A 到 B 之間沒有有效起點。start(即剩餘段的起點)一定能繞完整圈,因為前半段的「虧欠」會由後半段的「盈餘」補回。時間複雜度: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 的位置,等同於找前綴和序列的最小值點之後一位。數學推導嚴謹,但實作較貪心版繁瑣,兩者時間複雜度相同。