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: