134. Gas Station

Medium

Description

環形路線上有 n 個加油站，第 i 個加油站有 gas[i] 的油，從第 i 站到第 i+1 站消耗 cost[i] 的油。油箱容量無限。判斷從哪個站出發能繞一圈，回傳起始站索引；若不行回傳 -1。答案唯一。

Example:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Output: 3

Intuition#

如果總油量 >= 總消耗，一定有解；從第一個讓累計油量變負的下一站重新出發。

若 sum(gas) < sum(cost)，不可能繞一圈
若 sum(gas) >= sum(cost)，答案一定存在
從某站出發若在站 k 油量變負，則 0..k 之間任何站都不可能作為起點（因為從更前面出發到 k 時油量更多，都不行了）
所以從 k+1 重新嘗試

Approaches#

1: 暴力模擬#

概念: 嘗試從每個站出發，模擬繞一圈。
時間複雜度: O(n^2)
空間複雜度: O(1)

class Solution {
    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        val n = gas.size
        for (start in 0 until n) {
            var tank = 0
            var success = true
            for (step in 0 until n) {
                val i = (start + step) % n
                tank += gas[i] - cost[i]
                if (tank < 0) {
                    success = false
                    break
                }
            }
            if (success) return start
        }
        return -1
    }
}

⭐2: 一次遍歷 Greedy#

概念: 同時追蹤 totalTank 和 currentTank。若 currentTank < 0 就重設起點為下一站。最後檢查 totalTank >= 0。
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        var totalTank = 0
        var currentTank = 0
        var start = 0
        for (i in gas.indices) {
            val diff = gas[i] - cost[i]
            totalTank += diff
            currentTank += diff
            if (currentTank < 0) {
                start = i + 1
                currentTank = 0
            }
        }
        return if (totalTank >= 0) start else -1
    }
}

🔑 Takeaways#

Pattern: 貪心重設起點 — 局部失敗時跳過整個已嘗試區間
關鍵技巧: 「若 A 到 B 失敗，則 A 到 B 之間任何點到 B 都會失敗」是此題的核心推理；環形問題常用 totalTank 判斷全域可行性