# LeetCode Gas Station

2016-04-28 08:42:14      个评论    来源：DRFish

## 解题思路

``````c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...c[j]
c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...c[j]+c[j+1]
...
c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...c[j]+c[j+1]+...+c[n-1]``````

``````c[j]>=0
c[j]+c[j+1]>=0
...
c[j]+c[j+1]+...+c[n-1]>=0``````

``````c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...+c[j-2]
c[0]+c[1]+...+c[j-1]<=c[0]+c[1]+...+c[j-3]
...
c[0]+c[1]+...+c[j-1]<=c[0]``````

``````c[j-1]<=0
c[j-2]+c[j-1]<=0
...
c[1]+c[1]+...+c[j-1]<=0``````

``````c[j]+c[j+1]+...+c[n-1]+c[0]+c[1]+...+c[j-2]>=0
c[j]+c[j+1]+...+c[n-1]+c[0]+c[1]+...+c[j-3]>=0
c[j]+c[j+1]+...+c[n-1]+c[0]>=0``````

``````class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
if sum(gas) < sum(cost):
return -1
min_sum, min_index, total = 0, 0, 0
for i in range(len(gas)):
total += gas[i] - cost[i]
if min_sum > total:
min_sum, min_index = total, i + 1
return -1 if total < 0 else min_index

if __name__ == "__main__":
assert Solution().canCompleteCircuit([5], [4]) == 0
assert Solution().canCompleteCircuit([5, 1, 2, 3, 4], [4, 4, 1, 5, 1]) == 4``````