[LeetCode] Gas Station

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

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

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Tags: Greedy

Thoughts...

假设 有n个station，那么第一个坐标为 0（同样也为n,因为lis是首尾相接的环), 第n个坐标为 n-1.  

这类题目是纯思路类型的题目。
关于这个题解题思路网上已经有很多总结，核心就是一句话 ： 如果从Station_i 出发后，最远只到达了Station_j , 那么我们可以确定，起点一定不在 [Station_1, Station_j ] 这个闭区间。 所以可以从Station_(j+1) 作为起点从新开始排查。

如果这道题不是唯一起点呢？ 思路还应当是大同小异的。 以上法则依然试用，但是我们只能获得第一个符合要求的起点，对于剩下的合理的起点, 在第一个合理起点后的第一个点和终点前的一个点之间，重复搜索第一个起点的方法，直至排查至第Station_(n-1) 为止。算法复杂度worst case (全是合理起点)是O(n^2)。

这个题目更值得思考的地方是LeetCode上给的 tag -- Greedy
我个人也处在对Greedy的理解中，这类问题形势很多，如果简单的概括为 ：Make locally optimal solution in hope of reaching global optimization。 恐怕指导意义不大。

试用Greedy的一个必要条件是 : You need to make choices.

就此题而言，choice是针对于选择唯一起点。就目前我的理解而言，每当一个潜在起点被否定后，如何选择下一个起点呢？ 固然，根据我们对于规律的总结，我们知道该如何选择。 然而从Greedy的角度，是否也可以暗示同样的选择呢？

PYTHON CODE

def canCompleteCircuit(self, gas, cost):
        gas_left = 0
        start_station = 0
        i = -1
        if sum(gas) - sum(cost) < 0:
            return -1
        else:
            for g,c in zip(gas,cost):
                i+=1
                gas_left += (g-c)
                if gas_left < 0:
                    start_station = i+1
                    gas_left = 0
                    
        return start_station