# 134. Gas Station
###### tags: `leetcode` `134` `medium`

## :memo: Question

## :memo: 題意
* 有一個 gas station list，第一個 gas station 可以加的油為 gas[0]，然後要到下一站需要的油為 cost[0]，現在問你要從哪個加油站開始才能走遍整個加油站，起始的油為0。

## :memo: leetcode solution
* :medal: **思考一**: 我就每個 station 都當作起頭走一遍，只要我目前的油會變成負的我就換下一個起點。
*

## :memo: leetcode solution code

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 如果 cost 大於 gas 就一定無法走完，直接 return -1
        if sum(cost) > sum(gas):
            return -1
        
        for i in range(len(gas)):
            # 去看有走過哪些 station
            seen = [0 for i in range(len(gas))]
            j = i
            gas_value = 0
            while not seen[j]:
                gas_value += gas[j] - cost[j]
                seen[j] = 1
                
                if gas_value < 0:
                    break
                    
                j += 1
                
                if j >= len(gas):
                    j %= len(gas)
                    
            if gas_value >= 0:
                return i

## :memo: BigO
* 時間複雜度: O(len(gas)^2)，最差的狀況。
* 空間複雜度: O(len(gas))

## :memo: better solution

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

## :memo: BigO
* 時間複雜度: O(len(gas))
* 空間複雜度: O(1)