134. Gas Station
如果從 i 開始，會是
(gas[i] - cost[i]) + (gas[i+1] - cost[i+1]) + ... - cost[i-1]
所以其實只需要知道兩者的差。定義
A[i] := gas[i] - cost[i], for 0 <= i < n
我們把 A 再複製一遍接在後面，也就是
A[n+i] := A[i], for 0 <= i < n
可以發現，從 i 開始能夠成功的條件是
對所有 0 <= j < n，都有
A[i] + A[i+1] + ... + A[i+j] >= 0
(因為我們複製了一份在後面，像是 A[i-1] = A[n-i-1]，所以可以處理繞一圈回來的情況)
定義 prefix sum S 如下
S[0] = 0
S[i+1] = A[0] + ... A[i]
可以發現成功的條件變成對所有 0 <= j < n 都有
S[i+j+1] - S[i] = A[i] + A[i+1] + ... + A[i+j] >= 0
整理一下得到我們要對所有 0 <= j < n，都有
S[i+j+1] >= S[i]
所以我們實際上是要找一個很小的 prefix sum
考慮 S[0], ..., S[n-1] 的最小值的 index
假設是 i 好了，所以我們有
S[i] <= S[j], for 0 <= j < n
所以我們有
S[n+i] = A[0] + ... + A[n-1] + A[n] + ... + A[n+i-1]
= A[0] + ... + A[n-1] + A[0] + ... + A[i-1]
= S[n] + S[i]
<= S[n] + S[j]
所以 S[n+i] 也是 S[n], S[n+1], ..., S[2n-1] 中的最小值
接著考慮以下兩種情況
若 S[n] >= 0，則 S[i] 就是 S[0], ..., S[2n-1] 中的最小值
當然就一定是合法的
若 S[n] < 0, 則 S[i+n] < S[i]，所以不管哪個 i 都不合法
所以最後就變成
1. 如果 S[n] = A[0] + ... + A[n-1] < 0 則失敗回傳 -1
2. 否則回傳有最小 prefix sum 的 index
Racket Code: