134.-jia-you-zhan.md

134. 加油站

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

解法一：暴力

外层一次遍历，找消耗gas[i] - cost[i] >= 0的站开始（贪心），循环遍历数组，每次计算余量remain并累加，当remain < 0跳出。看能否走一圈

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for i in range(n):
            if gas[i] - cost[i] < 0:
                continue
            #找到出发处
            start = j = i  #记录起始位置
            remain = 0
            #遍历到i-1处
            while j%n != (i-1)%n:
                remain += gas[j%n] - cost[j%n]
                if remain < 0:
                    break              
                j += 1
            #若能回到出发点
            if remain + gas[j%n] - cost[j%n] >= 0:
                return start
        return -1

解法二：贪心法

1。首先明确一点，能跑完全程的前提是对所有的i，有：

$$ ∑gas[i] - cost[i] >= 0 $$

2。要找起点的就是从i开始，使其满足题意。由于1。的前提保证，假设到0到i站没油了，则i到end的剩余油量必能满足0到i的消耗（总和>=0，若0~i剩余油量<0，则i ~end剩余油量必>0)。由于题目只有一个解，应该找尽量后面的i（0到i消耗<0只能说明i到end的剩余满足前面的消耗，却不一定能开动，若有解需要尽可能遍历所有元素）

class Solution(object):
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        remain = 0  #计算全程剩余
        run = 0  #计算当前消耗
        start = 0  #记录起点
        for i in range(n):
            remain += gas[i] - cost[i]
            run += gas[i] - cost[i]
            #若当前消耗<0，起点后移
            if run < 0:
                start = i + 1
                run = 0
        return start if remain >= 0 else -1