[Leetcode]134: Gas Station

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

Problem :
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

一個環境路上有 n 個加油站，每個加油站有 gas[i] 的汽油，從第 i 個加油站到 i+1 個加油站需要花費 cost[i] 的汽油。
假設汽車可以裝無數的汽油，判斷一輛沒有油的汽車是否可以從某個加油站出發行駛一圈後返回該加油站。如果不行，return -1。

圖來自leetcode

Thoughts :
解釋example在幹嘛
從 index 3 (gas[3] = 4)開始到 gas[4] = 5，4 - cost(1) +5 =8
從 index 4 (gas[4] = 5)開始到 gas[0] = 1，8 - cost(2) +1 = 7
從 index 0 (gas[0] = 1)開始到 gas[1] = 2，7 - cost(3) +2 = 6
從 index 1 (gas[1] = 2)開始到 gas[2] = 3，6 - cost(4) +3 = 5
從 index 2 (gas[2] = 3)開始到 gas[3] = 4，5 - cost(5) +4 = 4

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

time complexity, space complexity