[LeetCode] 134. Gas Station (JS)

5 個月前

內容目錄 隱藏

題目

沿著環形路線有 n 個加油站，其中第 i 個加油站的汽油量為 gas[i] 。

您有一輛油箱無限的汽車，從 i 車站到下一個車站(i + 1)需要花費 cost[i] 汽油。你從第一個加油站開始帶著空油箱開始旅程。

給定兩個整數陣列 gas 和 cost ，如果你可以順時針方向繞一圈，則返回起始加油站的索引，否則返回 -1 。如果存在解，則保證它是唯一的。

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

解題思路

我最開始想的是先找到 gas[i] >= cost[i] 的 i 然後嘗試從 i 站出發看是否能夠跑完整個路線，如果不行就再找下一個 i。

根據範例可得出每站剩餘的汽油量計算公式為：sum - cost[i] + gas[i+1]，需要特別注意的是若 gas[i+1] 範圍超出了 gas 長度則需要從 0 開始。

但這樣做的時間複雜度會是 O(n²)，因為遍歷找到 i 之後還要再遍歷整個路線計算耗油量，送出會超時，所以得想其他的方法。

其實只需要一個循環就能解決了，不需要實際找到起始點後完整跑一遍路線：

計算整個旅程中的總油量減去總耗油量，如果最後小於0，那麼無論從哪個站開始都無法完成一圈。
計算從 start_index 到目前站的總油量減去總耗油量。如果在某個站 i 發現油量不足以到達下一站，則表示從start_index 到 i 中間的所有站都不可能是起始站，將start_index設定為 i + 1，並重置 curr_tank。
最後檢查 total_tank 是否大於等於0，如果是，則表示可以從start_index 完成一圈，因此返回 start_index；否則，無法完成一圈，返回-1。

完整程式碼

var canCompleteCircuit = function(gas, cost) {
    let totalTank = 0
    let currTank = 0
    let startIndex = 0
    
    for (let i = 0; i < gas.length; i++) {
        totalTank += gas[i] - cost[i]
        currTank += gas[i] - cost[i]

        if (currTank < 0) {
            startIndex = i + 1
            currTank = 0
        }
    }

    return totalTank >= 0 ? startIndex : -1
};