再复习贪心 leetcode 134 加油站

写这题之前，好好回顾下贪心解法：

1. 分发糖果 / 饼干，第一天写的内容。排序后，先从最小的孩子开始满足。
2. 跳跃数组。每次都选择跳最远的。
3. 硬币找零。每次都先找最大面额的。

然后今天这道题，我先写的手尾拼一起两层循序嵌套，能解出没超时但打败人很少。。。

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        twoGas = gas + gas
        twoCost = cost + cost
        i = 0
        oil = 0
        while i < len(gas):  
            oil = gas[i]
            for j in range(len(gas)):
                oil = oil - twoCost[i+j]
                if oil >= 0:
                    oil += twoGas[i+j+1]
                else:
                    break
            if oil >= 0:
                return i
            else:
                i += 1
        return -1

然后换用贪心试试。能否绕行一周，如果能绕行一周，走的距离是固定的，由此可大致蒙出用贪心。找贪心满足的条件吧，只有一个加油站能绕行一周或者没有，如果我开车的话，肯定会在剩油最少时加油而且尽可能加很多很多...剩油最少，然后下个站点加油，这就是条件，找剩油最少的站点！！！

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        restGas = 0
        minRestGas = 0
        i = 0
        station = 0
        while i < len(gas):
            restGas += gas[i] - cost[i]
            # minRestGas = min(minRestGas, restGas)
            if restGas < minRestGas:
                minRestGas = restGas
                station = i + 1
            i += 1
        return -1 if restGas < 0 else station