Leetcode Link: 134. 加油站 - 力扣（LeetCode）
题目
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，我们 保证 它是 唯一 的，要求你输出它。
解法一
思路：（自己的想法）就是看那些盈余的站能不能把后面亏空的站亏空的部分补上，但是注意的是连续的
贪心的点在于：我每次的起点只选择在前一站是亏空而当前站是盈余的站，即最大化我初始的盈余，然后依次向后更新当前盈余，直到盈余变成了亏空，开始下一次的寻找起点。
思路如下：
- 先求每个站剩多少（正数表盈余，负数表亏空）
- 要是每站剩的总和是负数，不用看了，肯定走不完
- 反之则从头遍历，利用贪心遍历每一个点并在有需要的时候更新开车的起点
- 在第 0 站，如果不亏空，就直接算是起点
- 如果开始亏空了，就找到一个新的起点，要求该起点前一站是亏空而当前站是盈余
- 如果当前有盈余，则更新盈余往下走
- 遍历结束后再从头遍历到3最后的起点，保证形成闭环
题解：
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
# 先求每站剩的油
remain = []
sum_remain = 0
for g, c in zip(gas, cost):
diff = g - c
sum_remain += diff
remain.append(diff)
if sum_remain < 0: # 累加亏空，在哪都不能返回
return -1
# 寻找起点
tmp_sum = -float('inf')
for p in range(len(remain)):
if p==0 and remain[p] >= 0:
tmp_sum = remain[p]
start = p
continue
if tmp_sum >= 0:
tmp_sum += remain[p]
continue
if tmp_sum < 0 and remain[p]-remain[p-1]>remain[p] and remain[p]>=0:
# 当前和小于0 并且 新到了一个 能够剩下或者恰好用完的地方 就开始新的计数
start = p
tmp_sum = remain[p]
continue
# 再从头遍历，检查能否形成闭环
p = 0
while(p<start):
tmp_sum += remain[p]
if tmp_sum < 0:
return -1
p += 1
return start
解法二
思路：随想录解法
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i 从 0 开始累加 rest[i]，和记为 curSum，一旦 curSum 小于零，说明 [0, i] 区间都不能作为起始位置，起始位置从 i+1 算起，再从 0 计算curSum。
如图： 
那么为什么一旦[i，j] 区间和为负数，起始位置就可以是j+1呢，j+1后面就不会出现更大的负数？
如果出现更大的负数，就是更新j，那么起始位置又变成新的j+1了。
而且j之前出现了多少负数，j后面就会出现多少正数，因为耗油总和是大于零的（前提我们已经确定了一定可以跑完全程）。
局部最优：当前累加 rest[j]的和 curSum 一旦小于 0，起始位置至少要是 j+1，因为从 j 开始一定不行。
全局最优：找到可以跑一圈的起始位置.
局部最优可以推出全局最优，找不出反例，试试贪心！
和解法一的不同
该解法判断起点的方式比我的操作起来简单，包括我的情况，但是又不会出错。 因为如果
curSum<0就一定会在下一个油量盈余的站开始新的起点（因为负数+正数还是负数的话说明之前就是负数，如果之前就是负数了，那么之前的下一站就是开始，然后就会一直找到第一个正数才算开始）
有一块有点难理解的是，他没有形成闭环，就去找了起点 题解说只要最后有盈余，就一定能跑完全程，是正确的，但是我觉得怪怪的。
题解：
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
cursum = 0
allsum = 0
start = 0
for p in range(len(gas)):
cursum += (gas[p] - cost[p])
allsum += (gas[p] - cost[p])
if cursum < 0:
start = p+1
cursum = 0
if allsum < 0:
return -1
else:
return start解法三
思路： 复习的时候想的思路
不知怎么的，冥冥之中认定了一个不能证明出来的结论
只要
sum(gas)>=sum(cost)，一定能走完；反之一定走不完。
gas-cost 得到结果就是每站净增的汽油，我们逐站累加（遍历），同时必需满足下面
油箱里的汽油不能是负数
否则就说明我们上一个选择的 start 不对，需要找到下一个净增为正的站点
由于我们认定了的结论，我们也不需要绕回去从头看了（我也不知道，就是感觉这样对，就没看，写出来就是对的）
题解：
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
# 先决条件
if sum(gas) < sum(cost):
return -1
# 每站净增
diff = [x-y for x, y in zip(gas, cost)]
# 遍历找起点，不能让left_gas小于0
left_gas = 0
start = 0
for i, val in enumerate(diff):
if left_gas < 0:
left_gas = val
start = i
else:
left_gas += val
return start