LeetCode 134. 加油站

◎

本节目标

用总量判定与负前缀排除法在线性时间确定环形加油站的起点。

这是局部约束与构造中“环形可行性”的母题：先判断总资源够不够，再利用局部失败排除一段起点。

题意与约束

第 i 个站可获得 gas[i] 单位油，驶向下一站消耗 cost[i]。在环上选择一个起点，油箱初始为零；返回起点则输出其下标，若不存在则输出 -1。

直接思路与瓶颈

逐个起点模拟一圈最直观，但每次失败前都可能走过很多站，最坏为 O(n²)。关键不是重新尝试每一个站，而是解释一次亏空能排除哪些起点。

贪心模型与算法推导

令 gain = gas[i] - cost[i]。总和小于零时全局油量不足，无解；否则从左到右累计当前油量 tank。若走到 i 后 tank < 0，就把起点改为 i + 1 并清零累计量。

正确性依据

若从当前起点到 i 的净收益为负，那么这段中任意更靠后的站作为起点，到达 i 时只会少掉此前的非负前缀或保留同样亏空，均不能通过 i。因此可一次排除整段。总和非负时，最后保留的起点补上此前被跳过的环形后缀仍不会亏空，故它可行。

样例执行过程

gas=[1,2,3,4,5]、cost=[3,4,5,1,2] 的净收益为 [-2,-2,-2,3,3]。前 3 次累计都为负，依次把起点移到 1、2、3；从 3 开始累计 3,6，绕回前面三个站后恰好回到 0，返回 3。

代码实现

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int> gas, vector<int> cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < static_cast<int>(gas.size()); i++) {
            const int gain = gas[i] - cost[i];
            total += gain;
            tank += gain;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total < 0 ? -1 : start;
    }
};

Python

Python 3

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total = tank = start = 0
        for index, (fuel, expense) in enumerate(zip(gas, cost)):
            gain = fuel - expense
            total += gain
            tank += gain
            if tank < 0:
                start = index + 1
                tank = 0
        return -1 if total < 0 else start

复杂度分析

只扫描一次，时间 O(n)；只维护常数个变量，额外空间 O(1)。

边界与易错点

• 总油量不足必须返回 -1，不能只依赖局部累计。
• tank 变负时起点是下一站，不是当前站。
• 单站且净收益非负时，起点为 0。

模式迁移

环形资源、前缀余额和可行起点问题常可先做总量判定，再在局部余额为负时批量排除一段候选。