LeetCode 134. 加油站

题目描述
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。题目保证如果有解，则解是唯一的。

示例 1：
输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出：3
解释：从 3 号加油站（索引为 3）出发，可以获得 4 升汽油，此时油箱 = 0 + 4 = 4 升。开往 4 号站，消耗 1 升，油箱剩 3 升。开往 0 号站，消耗 2 升，油箱剩 1 升。开往 1 号站，获得 2 升，油箱 3 升。开往 2 号站，消耗 4 升，油箱 -1 升？等等，这样计算是错的。我们重新严谨计算一下：

从索引 3 出发：

• 到站 3，加油 gas[3]=4，油箱 4，开往站 4 消耗 cost[3]=1，到达站 4 时油箱 3。
• 到站 4，加油 gas[4]=5，油箱 8，开往站 0 消耗 cost[4]=2，到达站 0 时油箱 6。
• 到站 0，加油 gas[0]=1，油箱 7，开往站 1 消耗 cost[0]=3，到达站 1 时油箱 4。
• 到站 1，加油 gas[1]=2，油箱 6，开往站 2 消耗 cost[1]=4，到达站 2 时油箱 2。
• 到站 2，加油 gas[2]=3，油箱 5，开往站 3 消耗 cost[2]=5，到达站 3 时油箱 0。正好行驶一圈，所以返回 3。

解题过程
这是一个典型的搜索+贪心问题，我们循序渐进地分析。

步骤1：理解核心条件
设从第 i 站到第 i+1 站的“净收益”为 gas[i] - cost[i]。要想完成一圈，必须满足两个条件：

1. 总油量不能为负：所有站的净收益之和 >= 0，即 sum(gas) >= sum(cost)。否则无论如何都不可能行驶完一圈。
2. 从某个起点出发，在行驶过程中油箱剩余油量不能为负。

步骤2：暴力搜索思路
最直接的方法是尝试每一个加油站作为起点，模拟行驶一圈，检查过程中油箱是否一直非负。时间复杂度 O(n²)，在 n 较大时会超时。

步骤3：贪心优化
我们可以通过一次遍历来找到起点，核心思想是：

• 用一个变量 total_tank 记录总净收益（即总剩余油量），用于判断是否有解。
• 另一个变量 curr_tank 记录从当前起点出发到当前位置的累积剩余油量。
• 如果从起点 start 出发到第 i 站时，curr_tank 变成负数，说明从 start 到 i 的任何一个站都不能作为起点（因为中间任何一点作为起点都会在 i 处断油）。此时我们重新尝试从 i+1 站作为新起点，并将 curr_tank 重置为 0。
• 遍历结束时，如果 total_tank >= 0，则最后设置的 start 就是唯一解；否则返回 -1。

步骤4：详细推导
以示例 gas = [1,2,3,4,5], cost = [3,4,5,1,2] 为例：

1. 计算净收益数组：[-2, -2, -2, 3, 3]
2. 初始化 start=0, curr_tank=0, total_tank=0。
3. 遍历：
   i=0: curr_tank += -2 = -2，变为负，说明从 0 出发不行。重置 start=1, curr_tank=0。
   i=1: curr_tank += -2 = -2，又为负，重置 start=2, curr_tank=0。
   i=2: curr_tank += -2 = -2，又为负，重置 start=3, curr_tank=0。
   i=3: curr_tank += 3 = 3，保持正。
   i=4: curr_tank += 3 = 6，保持正。
   此时 total_tank = (-2)3 + 32 = 0，满足条件。
   返回 start=3。

步骤5：算法正确性理解
为什么贪心是有效的？
因为如果从 A 点出发到 B 点油量不够，那么 A 到 B 之间的任何点作为起点，到达 B 点时油量只会更少（因为少了中间段的初始油量支持）。所以可以直接跳过中间点，从 B+1 重新尝试。

步骤6：代码实现
按照上述逻辑，我们可以写出 O(n) 时间、O(1) 空间的代码。

def canCompleteCircuit(gas, cost):
    n = len(gas)
    total_tank = 0
    curr_tank = 0
    start = 0
    for i in range(n):
        total_tank += gas[i] - cost[i]
        curr_tank += gas[i] - cost[i]
        if curr_tank < 0:
            start = i + 1
            curr_tank = 0
    return start if total_tank >= 0 else -1

总结
这个问题的关键是将“能否行驶一圈”转化为净收益的累积和问题，然后利用贪心选择起点，避免不必要的重复模拟。