[LeetCode] 134. Gas Station

轉自LeetCode

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

<Solution>
這題有個線性的解法，時間複雜度是O(N)

想法如下

• 用兩個指標分別代表起始點和終點，雙方向彼此靠近，當 start = end 的時候，代表所有點都已經走過

• 檢查 gas 的總量，如果大於等於零，代表可以全程走完；如果小於零，代表無法走完

這邊有個特別的地方要注意

在初始的時候，start = size() - 1，end = 0

這是要避免雙方向彼此靠近的時候，會有沒有檢查的點

行進方向都是從 start 走向 end

如果 start = 0，end = size() - 1

X         X         X         X         X         X
start->                                       <- end   (指標移動方向)

可以看到，當兩個指標互相靠近的時候，其實雙方的距離是變短的

因此會有少掉的點沒有檢查到，並且要去處理一些 corner cases

而如果 start = size() - 1，end = 0

X         X         X         X         X         X
end->                                       <- start   (指標移動方向)

當兩個指標互相靠近的時候，雙方的距離是拉長的，因此這樣會檢查到所有的點

code 如下(參考資料)
c++

kotlin