134. Gas Station.md

134. Gas Station

https://leetcode.com/problems/gas-station/

solution

• 暴力法

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for i in range(len(gas)):
            rest = gas[i] - cost[i]
            next_index = (i + 1) % len(gas)

            while rest > 0 and next_index != i:
                rest += gas[next_index] - cost[next_index]  # 注意这里是next_index
                next_index = (next_index + 1) % len(gas)
            
            if rest >= 0 and next_index == i:
                return i
        return -1

时间复杂度：O(n^2)
空间复杂度：O(1)

• 贪心

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost): 
            return -1
        
        tank = idx = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:
                tank = 0
                idx = i+1
        return idx

时间复杂度：O(n)
空间复杂度：O(1)