134. Gas Station

在一条环形的路上有N个加油站，每个加油站里有gas[i]的汽油，从第i个加油站到第i+1个加油站需要花费cost[i]的汽油。假设汽车的油箱可以装无数的汽油，判断一辆没有油的汽车是否可以从其中的某一个加油站出发并行驶一圈后返回该加油站。如果可以的话，返回起始加油站的下标，否则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        # 6 star, 非常巧妙，没做出来
        # 首先如果sum(gas) < sum(cost)肯定跑不完一圈的，如果sum(gas) >= sum(cost), 则必有一个解。
        # 从第一个开始作为起点，在每一站计算当前剩下的油left, 如果left加上当前油站的油还跑不完当前到下一个油站的距离，则设下一个油站为起点，
        # 继续这样检查直到遍历结束
        if sum(gas) < sum(cost):
            return -1
        left, index = 0, 0
        for i in range(len(gas)):
            if gas[i] + left < cost[i]: # 剩余的加当前的小于这一站需要消耗的，因此设下一站为起点，将剩余的油量重置为0
                index = i + 1
                left = 0
            else:
                left += gas[i] - cost[i] # 剩余的加当前的大于这一站消耗的，继续走到下一站
        return index