视频链接
https://algocasts.io/episodes/AEpoBEGQ
推论证明
推论：如果加油站的油量之和，大于等于消耗的油量之和，那么肯定存在一个出发点，可以绕行公路一周。
证明：加油站的油量数组是 gas，耗油数组是 cost。假设到达下标 i 时，以下前缀和达到最小值：
sum(i) = gas[0]-cost[0] + gas[1]-cost[1] +...+ gas[i]-cost[i]
其中，sum(i) 表示前缀和，同理我们有以下等式：
sum(i+1) = gas[0]-cost[0] +...+ gas[i]-cost[i] + gas[i+1]-cost[i+1]
上面两个等式相减，得到：
sum(i+1) - sum(i) = gas[i+1] - cost[i+1]
由于，sum(i) 是最小的前缀和，因此我们有以下不等式：
sum(i+1) >= sum(i)
sum(i+2) >= sum(i)
...
sum(n-1) >= sum(i)
对于以上所有不等式，把 sum(i) 移到左边，并将相同的部分抵消后，得到：
// 【不等式组 (1)】
gas[i+1]-cost[i+1] >= 0
gas[i+1]-cost[i+1] + gas[i+2]-cost[i+2] >= 0
...
gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1] >= 0
同理，对于 [0, i] 区间内的任意下标 j（0 <= j <= i），有以下不等式：
sum(j) >= sum(i)
不等式左右两边展开，得到：
gas[0]-cost[0] + gas[1]-cost[1] +...+ gas[j]-cost[j] >=
gas[0]-cost[0] + gas[1]-cost[1] +...+ gas[i]-cost[i]
左右两边都加上 gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]，得到：
gas[0]-cost[0] +...+ gas[j]-cost[j] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]
>=
gas[0]-cost[0] +...+ gas[i]-cost[i] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]
已知，加油站的油量之和，大于等于消耗的油量之和（这是给我们的条件），于是有：
// 【不等式组 (2)】
gas[0]-cost[0] +...+ gas[j]-cost[j] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]
>=
gas[0]-cost[0] +...+ gas[i]-cost[i] + gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1]
>= 0
结合【不等式组 (1)】和【不等式组 (2)】，我们得到以下一系列不等式（0 <= j <= i）：
gas[i+1]-cost[i+1] >= 0
gas[i+1]-cost[i+1] + gas[i+2]-cost[i+2] >= 0
...
gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1] >= 0
...
gas[i+1]-cost[i+1] +...+ gas[n-1]-cost[n-1] + gas[0]-cost[0] +...+ gas[j]-cost[j] >= 0
根据以上不等式可以知道，如果汽车从 i+1 出发，通过加油和耗油，到达每一站时，剩余油量都是非负数，所以汽车可以绕行公路一周。
证明完毕。