環形路線上有 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
TIP
如果總油量 >= 總消耗，一定有解；從第一個讓累計油量變負的下一站重新出發。
- 若
sum(gas) < sum(cost)，不可能繞一圈 - 若
sum(gas) >= sum(cost)，答案一定存在 - 從某站出發若在站 k 油量變負，則 0..k 之間任何站都不可能作為起點（因為從更前面出發到 k 時油量更多，都不行了）
- 所以從 k+1 重新嘗試
Approaches
1. Brute-Force Simulation — O(n^2) / O(1)
- Idea: 嘗試從每個站出發，模擬繞一圈。
- Time:
O(n^2) - Space:
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. Single-Pass Greedy — O(n) / O(1)
- Idea: 同時追蹤
totalTank和currentTank。若currentTank < 0就重設起點為下一站。最後檢查totalTank >= 0。 - Time:
O(n) - Space:
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: 貪心重設起點 — 局部失敗時跳過整個已嘗試區間
- Key trick: 「若 A 到 B 失敗，則 A 到 B 之間任何點到 B 都會失敗」是此題的核心推理；環形問題常用
totalTank判斷全域可行性