今天來分享一個中等難度的 LeetCode 題目 —— 加油站問題（Gas Station）。看到這道題的第一直覺是透過窮舉法來測試所有的起點，但也可以透過線性時間解法來優雅的解決這個問題。
題目說明
在一條環形公路上有 n 個加油站，第 i 個加油站有汽油 gas[i] 升。你的車油箱容量無限，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從某個加油站出發（初始油箱為空），給定兩個整數陣列 gas 和 cost，如果能環繞一周回到起點，則返回出發的加油站編號，否則返回 -1。如果存在解，則 保證 它是 唯一 的。
解題思路
這道題有個重要前提：如果有解，則解是唯一的。利用這點，我們可以設計一個 O(n) 的算法：
var canCompleteCircuit = function(gas, cost) {
let balance = 0; // 如果總油量大於總消耗，則可以跑完全程
let minIndex = 0, minBalance = 0; // 紀錄最小餘額(初始設為0，因為我們假設從索引0開始時的起始餘額為0)以及最小餘額出現後的下一個加油站
for(let i = 0; i < gas.length; i++){
balance += gas[i] - cost[i]; // 計算每站的油量變化
if(balance < minBalance){ // 如果油量餘額小於 0，則可以得知此處為最小餘額的位置
minBalance = balance; // 找到新的最小餘額點
minIndex = i + 1 // 紀錄最小餘額出現後的下一個加油站為可能起始點
}
}
return balance >= 0 ? minIndex : -1
};
關鍵變數
- balance：
- 用途：記錄從起點開始到當前位置的累計油量餘額
- 計算方式：每站獲得的油量(gas[i])減去前往下一站消耗的油量(cost[i])
- 意義：表示車子在行駛過程中的「油箱餘額」，正值表示有多餘的油，負值表示油不夠
- minBalance：
- 用途：記錄整個循環過程中遇到的最小餘額
- 初始值設為0是因為我們假設從0位置開始，初始餘額為0
- 意義：幫助找出最佳起點，因為最小餘額之後的位置可能是更好的起點
- minIndex：
- 用途：記錄最小餘額出現後的下一個位置
- 當找到新的最小餘額時會更新為當前位置+1
- 意義：這就是解決問題的關鍵 - 它標記了可能的最佳起點
總結
透過從油量最少的索引0的位置開始行駛，如果在某個加油站(balance)的油量變為負數，則可以確定由0出發不可行。由於環形路線的特性，如果總油量大於總消耗(balance > 0)，則必然存在一個起點可以完成環繞。
最小餘額點之後的位置是最佳起點，因為：
- 從這點出發，我們會先經過油量最充裕的部分
- 到達最小餘額點時，已經確保有足夠的油量才通過這個困難點
相較於窮舉法，此解法可以將時間複雜度從 O(n²) 降至 O(n)。
