刷到底 153 ～ 加油站

基本信息

• 题号：153
• 题厂：脸书
• 难度系数：中

有 n 个站，gas 数组代表该站可加油量，cost 代表从该站到下一站的耗油量。问：能不能靠着到站加油的方式循环一周？？如果可以返回开始地的 index，如果不行返回 -1

例如 gas = [1,2,3,4,5], cost = [3,4,5,1,2]，我们可以从第 4 站（index 为 3）开始循环一周，于是返回 3……

解题思路

• 要想循环一周，肯定需要加油量大于等于耗油量才行；
• 确定油量能否绕场一周后，我们再开分析到底要从那一站加油才能绕场一周？？

例如：我在 A 站加油 1，但是需要耗油 2 才能到下一站，于是 A 站就不能成为起点……

• 要想成为起点需要满足两个条件：

1. 该站的加油量大于耗油量；
2. 从该站开始后，在后续站台不会出现盈余不够的情况，即存油量小于 0

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 创建 accum 和 balance 变量。accum 记录绕场一周的总耗油量/加油量，balance 记录当某站 i 加油量大于耗油量时，剩余油量能否支撑到终点……
        # res = -1 代表还没有找到可以加油的起始站
        res = -1
        accum, balance = 0, 0
        
        for i in range(len(gas)):
            gap = gas[i] - cost[i]
            accum += gap
            
            # 如果本站加油量有盈余且 res 等于 -1，可以进入该站 balance 考察周期
            # 后续过程中，balance 都要更具盈余增减
            if gap >= 0 and res == -1:
                res = i
                balance = gap
            elif res >= 0:
                balance += gap
            
            # 循环结束前如果出现 balance 小于 0 的情况，说明该起点 i 不能支撑全场，需要清零重制 balance 和 res
            if balance < 0:
                res = -1
                balance = 0
        
        # 循环结束后如果累积油量大于等于 0 则返回 res，否则返回 -1           
        return res if accum >= 0 else -1

Constraints

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

除了取值范围外，还可以和考官讨论一下加油起点会不会出现多种可行情况……

Big O

• Time：O（ n ）
• Space：O（1）

测试

• 当 k = 1 时；
• ……

总结

• 本题可作为「贪心算法」重点题目定期复习，熟悉「贪心算法」分析思路……