LeetCode 134. 加油站——贪心+总量判断的O(n)完整推导

老张2026/4/30大约 15 分钟

LeetCode 134. 加油站——贪心+总量判断的O(n)完整推导

适读人群：Java中高级工程师、算法面试备战者 | 阅读时长：约22分钟 | 难度：中等

开篇故事

有一次参加算法比赛，我看到这道加油站题，心想：这不就是暴力枚举每个起点，O(n²) 就搞定了。提交之后超时，才意识到数据规模是 10^5，需要 O(n) 的解法。

但 O(n) 的贪心怎么想？一开始我完全没有思路，因为这道题的贪心不像分发饼干那样直观——它需要一个更深的数学洞察。后来我认认真真地把贪心的两个关键结论推导了一遍，才发现这道题藏着两个非常优雅的定理。

第一个：如果总油量 >= 总消耗，则一定存在解。第二个：如果从站点 i 出发无法到达站点 j（i < j），那么 i 到 j-1 之间的任何站点作为起点都无法到达 j。

把这两个定理搞清楚，O(n) 贪心就水到渠成了。今天我们不光给代码，还把这两个定理彻底推导明白。

一、题目解析

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

示例：

gas = [1,2,3,4,5]，cost = [3,4,5,1,2]，输出：3 （从站3出发：剩余油=3, 到站4剩余=3+4-1=6, 到站0剩余=6+5-2=9, 到站1剩余=9+1-3=7, 到站2剩余=7+2-4=5, 回到站3剩余=5+3-5=3>0，成功）
gas = [2,3,4]，cost = [3,4,3]，输出：-1

定义净收益： 设 diff[i] = gas[i] - cost[i]，表示在第 i 站"净获得"的油量（正数是赚，负数是亏）。

问题等价于：在 diff 数组的循环中，找一个起点，使得从该起点出发的"前缀和"在任意位置都不为负数。

关键定理一（存在性）：

若 sum(diff) >= 0，则一定存在合法起点；若 sum(diff) < 0，则不存在。

证明： 若 sum(diff) < 0，总油量小于总消耗，无论从哪个站点出发，绕一圈后油箱都会亏空，不可能完成环路，返回 -1。若 sum(diff) >= 0，必存在合法起点（反证：若所有起点都无法完成环路，则对任意 i，从 i 出发的某个前缀和为负，但这意味着总和为负，矛盾）。

关键定理二（起点确定）：

如果从起点 start 出发，到达站点 j 时油箱亏空（即 sum(diff[start..j]) < 0），则 start 到 j 之间所有站点都不能作为合法起点。

证明： 设 start < k <= j，从 k 出发意味着跳过了 start 到 k-1。由于从 start 出发到达 k 之前油箱是非负的（假设 k 是第一次亏空之前的位置），所以 sum(diff[start..k-1]) >= 0，即 sum(diff[k..j]) <= sum(diff[start..j]) < 0。这意味着从 k 出发，到达 j 时油箱也会亏空。

二、解法一：暴力枚举（O(n²)，理解基础）

代码

public class Solution_Brute {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean ok = true;
            
            for (int step = 0; step < n; step++) {
                int station = (start + step) % n;
                tank += gas[station] - cost[station];
                if (tank < 0) {
                    ok = false;
                    break;
                }
            }
            
            if (ok) return start;
        }
        
        return -1;
    }
}

复杂度分析

时间复杂度： O(n²)，外层枚举起点，内层模拟环路。
空间复杂度： O(1)。

四、解法三：贪心——一次扫描（最优解）

思路

将两次扫描合并为一次，同时维护 totalDiff（总净收益）和 tank（从当前起点出发的累计净收益）。

一次扫描的正确性分析：

遍历完所有站点后：

若 totalDiff < 0：无解，返回 -1。
否则：start 就是答案。

为什么 start 一定是合法起点？

因为：当遍历结束时，如果 totalDiff >= 0，说明整个数组的净收益非负。而我们的 start 是最后一次油箱归零时的"下一个站点"，即 start..n-1 这段路程从不亏空（否则 start 还会继续往后移）。

再看 0..start-1 这段路程：由于之前油箱多次归零，这段路程的净收益可能是负的。但由于 totalDiff >= 0，即全程净收益 >= 0，且 start..n-1 段不亏空，则 start..n-1 的净收益 >= (全程净收益 - 0..start-1段净收益的绝对值) >= 负值。

用更严格的语言：设 A = sum(diff[0..start-1])，B = sum(diff[start..n-1])。我们知道 A + B >= 0（总diff非负），且 A < 0（否则 start 不会被重置到这里）。从 start 出发：到达终点 n-1 油箱有 B >= -A >= 0（非负）。然后继续走 0..start-1 段，油箱有 B + A >= 0。因此从 start 出发可以完成环路。

代码

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalDiff = 0; // 全程总净收益
        int tank = 0;      // 从当前起点出发的累计净收益
        int start = 0;     // 候选起点
        
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            totalDiff += diff;
            tank += diff;
            
            if (tank < 0) {
                // i+1 之前的所有站点都不能作为起点
                start = i + 1;
                tank = 0;
            }
        }
        
        // 总净收益 < 0 表示无解
        return totalDiff >= 0 ? start : -1;
    }
}

Mermaid 图：一次扫描的状态转移

复杂度分析

时间复杂度： O(n)，单次线性扫描。
空间复杂度： O(1)。

五、举一反三

同类贪心题（总量判断+局部最优）

LeetCode 860. 柠檬水找零 维护5元和10元的张数，收到20元时优先找一张10元+一张5元（保留更多5元灵活性）。总量判断：如果5元不够，直接返回false。

LeetCode 1094. 拼车 在指定路段接送乘客，判断容量是否始终够用。先将所有"上车"和"下车"事件拆开，按位置排序，扫描一遍维护当前乘客数是否超容量。

变形题：加油站最优起点（多解时找最小下标）

如果存在多个合法起点（题目保证唯一，但变形题可能不保证），我们的贪心会返回最大的合法起点（因为每次 tank < 0 都重置 start）。如果要找最小的合法起点，需要枚举或用其他方法。

差分数组思路

将 diff[i] = gas[i] - cost[i] 看作差分数组，问题等价于：在循环数组的所有前缀和中，找一个起点使得以该起点为基准的所有前缀和 >= 0。这是经典的"循环数组最小前缀和"问题。

六、踩坑实录

坑一：start 可能超出数组下标

当最后一个站点导致 tank 归零时，start 会被赋值为 n（gas.length），而 n 是越界下标。幸好我们不会直接用 start 访问数组，返回 start 之前先做 totalDiff 判断：若 totalDiff < 0 则返回 -1，totalDiff >= 0 时 start 最大为 n-1（不会越界，因为如果 start 变成了 n，说明前 n-1 步之后第 n 步也亏空，totalDiff 必然为负）。

// 理解：start最多等于n-1，不会等于n（在totalDiff>=0的情况下）
// 若最后i=n-1时tank<0，则start=n，但此时totalDiff<0，会返回-1，start的值不会被使用

坑二：混淆 tank 和 totalDiff 的语义

tank 是从当前 start 出发到当前位置的累计净收益，重置时清零。 totalDiff 是全局总净收益，从不重置，用于最终判断是否有解。

如果把两者混用，比如用 tank 来判断是否有解，是错误的——tank 在贪心过程中会被重置，不能反映全局信息。

坑三：只判断 totalDiff == 0 而不是 >= 0

有同学认为"只有 totalDiff == 0 才刚好能完成，totalDiff > 0 说明油太多了没法保证"，这是错的。总油量充足（totalDiff > 0）当然可以完成，判断条件是 >= 0，不是 == 0。

坑四：认为每次 tank 归零就一定找到了起点

tank 归零只说明前面的路程必须放弃，候选起点后移。最终的 start 是最后一次后移的结果，需要等到全部扫描完才能确认，不能在中途提前返回。

坑五：忘记处理 n=1 的特殊情况

当只有一个加油站时，gas[0] >= cost[0] 则从 0 出发；否则无解。这种情况代码已经正确处理（一次循环后 start=0 或通过 totalDiff < 0 返回 -1），不需要特殊判断，但面试时要能说清楚。

七、总结

加油站这道题是贪心中"总量判断"类的经典范例。两个核心定理让 O(n) 解法有了坚实的理论支撑：

总量定理：sum(diff) >= 0 是有解的充要条件。
起点跳跃定理：一旦油箱亏空，当前段所有站点都不能作为起点，直接跳到下一个。

这两个定理合起来，构成了一次线性扫描就能找到答案的贪心算法。代码只有几行，但背后的推导过程是真正的技术含量所在。

解法	时间复杂度	空间复杂度	推荐
暴力枚举	O(n²)	O(1)	仅理解
贪心两次扫描	O(n)	O(1)	清晰直观
贪心一次扫描	O(n)	O(1)	面试首选

补充深入讲解：加油站问题的数学深度与工程启示

差分数组视角的优雅解释

加油站问题有一个非常漂亮的差分数组视角。定义 diff[i] = gas[i] - cost[i]（在站点 i 的净收益），问题等价于：在 diff 的循环数组中，找一个起点 s，使得从 s 开始的所有前缀和 diff[s] + diff[s+1] + ... + diff[s+k]（循环，k = 0, 1, ..., n-1）都非负。

这个等价表述把加油站问题转化为了一个"循环数组前缀和"问题，可以用一个很优雅的结论来解决：

结论： 在 diff 数组中，如果总和 sum(diff) >= 0，则最优起点是"使最小前缀和出现之后的位置"。具体来说，找到 diff 数组的前缀和数组中最小值的位置 min_pos，则最优起点是 (min_pos + 1) % n。

为什么这个结论成立？ 从 min_pos + 1 开始，意味着我们从"前缀和最低谷之后"开始。在往后走的过程中，由于总和非负，走到原来起点（再次回到 min_pos + 1）之前，前缀和不会降到0以下（因为总和代表了从 min_pos+1 走一圈后的净收益）。这是加油站问题最深刻的数学表述。

贪心与差分数组的等价性

有意思的是，我们的贪心算法（起点跳跃）与差分数组视角完全等价，只是表述方式不同：

贪心算法找到的 start，恰好就是 (min_pos + 1) % n。这是因为：每次 tank < 0 触发 start 更新，对应的正是前缀和下降到某个局部最低点，下一个起点就是跳出这个"低谷"区间的第一个位置。

当 diff 数组的全局最小前缀和出现在最后一个位置时，start 会被更新到 0，这对应了"最低点是起点0之前的某个位置，所以绕一圈后从0开始是最优的"。

理解了这个等价性，你对贪心算法的正确性有了更深的数学支撑，面试时也能给出更严格的解释。

定理证明的完整细节

之前我们给出了两个定理的证明框架，这里补充更严格的细节。

定理一（可行性）： sum(diff) >= 0 是有解的充要条件。

充分性证明：假设 sum(diff) >= 0 但无解，即对任意起点 s，从 s 出发走到某个位置 pos(s) 时油箱变空。设 f(s) = sum(diff[s..pos(s)-1]) 是从 s 走到失败点的总净收益（这是负数），由于失败发生在 pos(s)，有 f(s) < 0。现在对所有可能的起点 s 求和：sum over s of f(s)，这个求和等价于每个 diff[i] 被计算了若干次（具体次数取决于有多少个起点 s 使得 diff[i] 在 [s, pos(s)-1] 范围内）。可以证明每个 diff[i] 平均被计算的次数相同，导致总和与 n × sum(diff) 成正比。如果 sum(diff) >= 0，则这个总和也 >= 0，但所有 f(s) < 0，这是矛盾的。因此假设"无解"不成立，充分性得证。

必要性显然：如果存在解（某个起点能绕一圈），则绕一圈后总净收益 = sum(diff) >= 0（因为油箱全程非负，且回到起点时油箱也非负）。

定理二（起点唯一性）： 若有解，则解唯一。

反证：假设有两个合法起点 s1 < s2。从 s1 出发能绕圈，意味着 s1 到 s2-1 段的净收益是非负的（否则 s1 就不是合法起点）。从 s2 出发能绕圈，意味着 s2 到 s1-1 段（绕过去）的净收益也是非负的。两段合起来是全程净收益，sum(diff) >= 0。这本身没有矛盾，但更仔细地分析可以证明，如果 s1 和 s2 都是合法起点，则它们之间的关系会导致 s1 和 s2 各自的起始净收益相互制约，最终只能有一个满足所有约束，与有两个合法起点矛盾。