動機

greedy都是一種特別的想法，從一個等式或不等式開始

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

 

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]Output: 3Explanation:Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4Travel to station 4. Your tank = 4 - 1 + 5 = 8Travel to station 0. Your tank = 8 - 2 + 1 = 7Travel to station 1. Your tank = 7 - 3 + 2 = 6Travel to station 2. Your tank = 6 - 4 + 3 = 5Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]Output: -1Explanation:You can't start at station 0 or 1, as there is not enough gas to travel to the next station.Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4Travel to station 0. Your tank = 4 - 3 + 2 = 3Travel to station 1. Your tank = 3 - 3 + 3 = 3You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.Therefore, you can't travel around the circuit once no matter where you start.

 

Constraints:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 104
  • 0 <= gas[i], cost[i] <= 104

Sol

如果要能走完一圈，gas的總和一定大於cost的總和

那起點是? 在走的時候一定不會讓gas與cost的差額小於0

如果說起點一定在的話，就從起點開始走，看目前的gas總和與cost總和的差，是不是小於0，如果小於零，就把起點設定成目前的位置的下一位

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        ret = 0
        i = 0
        tank = 0
        cnt = 0
        while i < len(gas):
            tank += gas[i]-cost[i]
            cnt += gas[i]-cost[i]
            if tank < 0:
                ret = (i+1)%len(gas)
                tank = 0
            i+=1
        return ret if cnt >= 0 else -1