134. 加油站

class Solution:
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        n = len(gas)        
        total_tank, curr_tank = 0, 0
        starting_station = 0
        for i in range(n):
            total_tank += gas[i] - cost[i]
            curr_tank += gas[i] - cost[i]
            if curr_tank < 0:
                starting_station = i + 1
                curr_tank = 0
        
        return starting_station if total_tank >= 0 else -1

       其实可以用贪心的方法来解决，get[ i ]代表从 i 加油站到 i+1 加油站油量的变化。也就是路过每个加油站油箱里的油是少了还是多了。贪心的方法就是考虑，从头开始找到消耗油最多的那个区间也就是油箱里的油最少的而且是负数，如果在这个区间里出发肯定是不能走一圈的。

       如果油箱里的油一直是正数，说明一直有油，那就不用考虑变换起始的加油站了。只有油箱的油是最小的负数，说明从0到目前这个加油站里是没有起始加油站能走完一圈的，因为它连目前这段都走不完。因为这个区间里取一个 i 加油站，假如 i 前面的油量是正的，那从 i 出发肯定走不出区间，如果前面是负的，从 i 出发相当于加上前面数值，但是这个数值肯定小于这段区间最小的油量也就是区间尾的油量，加上之后，区间尾的油量仍然是负的，依然走不出这个区间。

       只能从这段加油站之后的第一个加油站重新尝试了。但是不是说，这样就一定能走完，因为这段之后的油量不一定能覆盖前面这一段里亏油量。所以需要用所有加油站gas量减去cost量的正负来判断。如果是正数，说明整体加油站储油量是足够的。

class Solution:
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        n = len(gas)        
        get = [None for _ in gas]
        for i in range(n):
            get[i] = gas[i]-cost[i]
        min = 0
        sum = 0
        ind=0
        for i in range(n):
            sum += get[i]
            if sum<=min:
                min = sum
                ind =i+1
        if sum>=0:
            return ind%n
        else:
            return -1