加油站（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

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1

提示：

• n == gas.length == cost.length
• 1 <= n <= 10⁵
• 0 <= gas[i], cost[i] <= 10⁴
• 输入保证答案唯一

解题思路：从暴力到贪心

设 diff[i] = gas[i] - cost[i]，表示第 i 站的净收益。

暴力做法是枚举每个起点模拟跑一圈，O(n²)。优化的关键在于：

核心推论： 从 0 出发，若在位置 k 时累计油量 curr 第一次跌破 0，则从 0 到 k 之间任意位置 j 出发也一定在 k 处失败。

证明：

从 j 出发到达 k 时的油量
= diff[j] + ... + diff[k]
= (diff[0]+...+diff[k]) - (diff[0]+...+diff[j-1])
=    curr_at_k ( < 0 )  -   curr_at_(j-1) ( ≥ 0 )
< 0

因此 curr < 0 时可直接跳过 [0, k]，将 start 推到 i+1。同时用 sum 累加所有 diff[i]：sum < 0 说明无解，sum ≥ 0 时 start 即为答案。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int sum = 0, start = 0, curr = 0;
        for (int i = 0; i < n; i++) {
            int diff = gas[i] - cost[i];
            sum += diff;
            curr += diff;
            if (curr < 0) {
                start = i + 1;
                curr = 0;
            }
        }
        return sum >= 0 ? start : -1;
    }
};

python

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n: int = len(gas)
        diff: List[int] = [0] * n
        total: int = 0
        curr: int = 0
        start: int = 0
        for i in range(n):
            diff[i] = gas[i] - cost[i]
            total += diff[i]
            curr += diff[i]
            if curr < 0:
                curr = 0
                start = i + 1
        if total < 0:
            return -1
        return start

go

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)
    sum, start, curr := 0, 0, 0
    for i := 0; i < n; i++ {
        net := gas[i] - cost[i]
        sum += net
        curr += net
        if curr < 0 {
            start = i + 1
            curr = 0
        }
    }
    if sum < 0 {
        return -1
    }
    return start
}

java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sum = 0, start = 0, curr = 0;
        for (int i = 0; i < n; i++) {
            int net = gas[i] - cost[i];
            sum += net;
            curr += net;
            if (curr < 0) {
                start = i + 1;
                curr = 0;
            }
        }
        if (sum < 0) return -1;
        return start;
    }
}

时间 O(n)，空间 O(1)。