[数据结构与算法]加油站-贪心134-python

class Solution:
    def canCompleteCircuit(self, gas, cost):
        # 如果总加油量小于总耗油量，那一定无法行驶一周
        # 反之则一定可以行驶一周
        if sum(gas) < sum(cost):
            return -1
        
        '''
        算法思路：如果x到不了y+1（但能到y），那么从x到y的任一点出发都不可能到达y+1。
        因为从其中任一点出发的话，相当于从0开始加油，而如果从x出发到该点则一定还有剩余的油。
        既然不从0开始都到不了y+1，那么从0开始就更不可能到达y+1了。
        
        变量：
        n：加油站数量。
        start：假定的起点。
        end：以start为起点所能到达的终点。
        rest：到达某加油站后剩余的汽油

        while循环：
        1. mid相当于行驶途中到达的加油站，不能直接用end是因为end可能大于n-1而造成数组下标溢出；
        2. 到达一个地铁站，rest算一下这一站的加油和下一站的耗油，end += 1；
        3. 当rest < 0，说明从start到不了end，则将start置为end；
        4. 当end > n-1 且 end % n == start时，说明汽车从起点成功行驶一周，返回start即可
        '''

        start = 0
        end = 0
        n = len(gas)
        rest = 0
    
        while start < n:
            mid = end % n
            rest += gas[mid] - cost[mid]
            end += 1
            
            if rest < 0:
                start = end
                rest = 0
            
            if end > n - 1 and end % n == start:
                return start