LeetCode 134 - 加油站（Gas Station）

问题描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。如果题目有解，该答案即为唯一答案。

示例 1：

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 = 3 升汽油
开往 0 号加油站，此时油箱有 3 + 5 - 2 = 6 升汽油
开往 1 号加油站，此时油箱有 6 + 1 - 3 = 4 升汽油
开往 2 号加油站，此时油箱有 4 + 2 - 4 = 2 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可以作为起始索引。

示例 2：

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 = 1 升汽油
开往 1 号加油站，此时油箱有 1 + 2 - 3 = 0 升汽油
开往 2 号加油站，你需要消耗 4 升汽油，但是你的油箱只有 0 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

约束：

gas.length == n
cost.length == n
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4

错误解法与分析

我的初始解法是暴力枚举每个可能的起始位置：

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)

    for start := 0; start < n; start++ {
        cnt := 0
        cur := start
        remain := 0
        for cnt < n {
            remain += gas[cur]
            remain -= cost[cur]
            if remain < 0 {
                break
            }
            cur = (cur + 1) % n
            cnt++  // ❌ 错误点：每次都要完整遍历一圈，导致 O(n²) 复杂度
        }

        if cnt == n {
            return start
        }
    }

    return -1
}

错误原因分析

这个解法在以下测试用例中会超时：

1
2
3

输入：gas = [1,1,1,...,1] (10^5个1), cost = [2,2,2,...,2] (10^5个2)
预期输出：-1
时间复杂度：O(n²) = O(10^10) → 超时！

关键问题：

时间复杂度过高：对于每个起始位置，都要尝试绕完整个环路，最坏情况下是 $O(n^2)$
重复计算：没有利用之前计算的结果，存在大量重复计算
缺乏剪枝：没有利用问题的数学性质进行优化

当 $n = 10^5$ 时，$O(n^2) = 10^{10}$ 次操作，必然超时。

正确解法 - 贪心算法

经过分析，我发现了几个关键洞察：

核心洞察

总量判断：如果 $\sum gas[i] < \sum cost[i]$，无论从哪里开始都不可能完成一圈
唯一性：如果能完成一圈，起始点是唯一的
关键定理：如果从位置 start 开始，能到达位置 i 但无法到达 i+1，那么从 start 到 i 之间的任何位置作为起点都无法到达 i+1

定理证明

假设从位置 $j$（$start \leq j \leq i$）开始能到达 $i+1$，设：

从 $start$ 到 $j-1$ 的净收益：$sum_1 \geq 0$
从 $j$ 到 $i$ 的净收益：$sum_2$
第 $i$ 站的净收益：$diff_i = gas[i] - cost[i]$

从 $start$ 开始到达 $i$ 但无法到达 $i+1$：
$$sum_1 + sum_2 + diff_i < 0$$

从 $j$ 开始能到达 $i+1$：
$$sum_2 + diff_i \geq 0$$

这导致矛盾：$sum_1 < 0$，但我们知道从 $start$ 能到达 $j-1$，所以 $sum_1 \geq 0$。

算法实现

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)
    tank := 0    // 当前油箱剩余
    total := 0   // 总的汽油量与消耗量的差值
    start := 0   // 起始位置

    for i := 0; i < n; i++ {
        diff := gas[i] - cost[i]
        tank += diff
        total += diff

        // 如果当前油量不够，说明从start到i都无法作为起始点
        // 下一个可能的起始点是i+1
        if tank < 0 {
            start = i + 1
            tank = 0
        }
    }

    // 如果总的汽油量小于总消耗量，无解
    if total < 0 {
        return -1
    }

    return start
}

算法执行过程

以 gas = [1,2,3,4,5], cost = [3,4,5,1,2] 为例：

i=0: diff=-2, tank=-2, total=-2, tank<0 → start=1, tank=0
i=1: diff=-2, tank=-2, total=-4, tank<0 → start=2, tank=0  
i=2: diff=-2, tank=-2, total=-6, tank<0 → start=3, tank=0
i=3: diff=3,  tank=3,  total=-3, tank≥0 → 继续
i=4: diff=3,  tank=6,  total=0,  tank≥0 → 继续

最终 total=0≥0，返回 start=3

方法比较

方面	暴力解法	贪心算法
时间复杂度	$O(n^2)$	$O(n)$
空间复杂度	$O(1)$	$O(1)$
核心思想	枚举所有起始位置	利用数学性质剪枝
是否超时	❌ 大数据量超时	✅ 高效通过
实现难度	简单直观	需要理解贪心思想
推荐度	★★☆☆☆	★★★★★

复杂度分析

时间复杂度：$O(n)$

只需要遍历一次数组，每个元素访问一次。

空间复杂度：$O(1)$

只使用了常数个额外变量：tank、total、start。

关键收获

贪心算法的本质：利用问题的数学性质，避免重复计算
优化思路：从 $O(n^2)$ 到 $O(n)$ 的关键是找到剪枝条件
证明的重要性：理解为什么贪心策略是正确的
实际应用：类似的"环形数组"问题都可以用这种思路优化

常见陷阱

❌ 忽略总量检查，导致错误判断
❌ 没有重置 tank 为 0，导致累积错误
❌ 边界条件处理不当（如空数组）

Adrian Wang's blog