LeetCode - Gas Station（加油站）

題目描述

在一條圓形路線上有 n 個加油站，其中第 i 個加油站的汽油量是 gas[i]。你有一輛油箱無限大的汽車，它從第 i 個加油站到第 i + 1 個加油站所需要的汽油量是 cost[i]。你必須從某個加油站出發，並且沿著順時針方向走一圈。如果可以走完整圈，返回出發的加油站的索引（從 0 開始），否則返回 -1。

範例：

輸入：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出：3
解釋：
從加油站 3 出發可以走完整圈，剩餘的汽油依次為：
  4 - 1 = 3, 3 + 5 - 2 = 6, 6 + 1 - 3 = 4, 4 + 2 - 4 = 2, 2 + 3 - 5 = 0

輸入：gas = [2,3,4], cost = [3,4,3]
輸出：-1
解釋：不管從哪個加油站出發，都無法走完整圈。

解法思路

此問題可以轉換為尋找從哪個加油站出發，能夠在扣除每段距離的油耗後，仍然保持汽油不為負並完成整圈。為此，我們可以使用貪心算法，根據汽油的盈虧變化來確定起點。

1. 總油量判斷：如果所有加油站的總汽油量 sum(gas) 小於總花費 sum(cost)，則無法走完整圈，直接返回 -1。

2. 逐站遍歷：如果 sum(gas) >= sum(cost)，則一定有解。從第一站開始，依次累加每個加油站的淨油量（gas[i] - cost[i]）：

   • 若當前總和 tank 為負，說明無法從起點到當前加油站，則將下一站作為新的起點。
   • 重新開始的原因是：如果到達某個加油站時，總和變為負數，說明從該段起始位置無法抵達這裡；因此可以從下一站開始。

範例代碼

以下是 Python 的實現：

def canCompleteCircuit(gas, cost):
    total_tank = 0      # 記錄總的油量差
    current_tank = 0    # 當前路段的油量差
    start_station = 0   # 起始加油站索引

    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]

        # 如果當前油量差小於 0，則無法從 start 到達 i
        if current_tank < 0:
            start_station = i + 1  # 將下一站設為新的起點
            current_tank = 0       # 重置當前油量差

    # 如果總油量差大於等於 0，則說明存在解
    return start_station if total_tank >= 0 else -1

代碼解析

1. 總和檢查：如果所有加油站的總油量 total_tank 大於或等於總成本，則至少有一個解。
2. 循環遍歷：
   • 累加每個加油站的淨油量差。
   • 當 current_tank 小於 0 時，更新起始站並重置 current_tank。
3. 返回結果：若 total_tank >= 0，則返回 start_station；否則返回 -1。

時間和空間複雜度

• 時間複雜度：O(n)，其中 n 是加油站的數量，我們僅需一次遍歷。
• 空間複雜度：O(1)，只需使用常數空間來存儲變量。