134. 加油站

1. 题目简介

难度：中等，原题链接：134. 加油站。

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

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

给定两个整数数组 gas 和 cost，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。如果存在解，则保证它是唯一的。

2. 问题分析

总油量小于总耗油量时，一定无法绕行一周；总油量足够时，可以通过一次扫描找到起点。关键是：某个起点走不通时，能否一起排除后面的一段起点。

汽车到达第 i 站后，先获得 gas[i]，再消耗 cost[i] 前往下一站。用 total 表示到站时的剩余油量，能够继续行驶的条件是：

total + gas[i] - cost[i] >= 0

假设从第 s 站出发，第一次在第 j 站发现油不够开到下一站，那么 s 到 j 都不能作为起点。原因是，从 s 到中间任意一站 k 时，剩余油量都不小于 0；即使带着这些油，从 k 走到 j + 1 都会失败，从 k 空油箱出发就更不可能成功。

因此，扫描时用 res 保存候选起点，用 totalTank 累加从该起点开始的 gas[i] - cost[i]。一旦 totalTank 为负，就把候选起点改为 i + 1，并把油量清零。已经排除的起点不需要重新尝试。

扫描结束后，最后一个候选起点就是累计油量差达到最低点之后的位置。从这里往后走不会缺油；绕回数组开头后，总油量足够这一条件又保证能够回到起点。代码先检查总油量，再执行这次扫描。

3. 代码实现

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

        int res = 0;
        totalTank = 0;
        for (int i = 0; i < n; i++) {
            totalTank += gas[i] - cost[i];
            if (totalTank < 0) {
                res = i + 1;
                totalTank = 0;
            }
        }
        return res % n;
    }
}

4. 复杂度分析

• 时间复杂度：O(n)，两次扫描分别检查总油量和选择起点。
• 空间复杂度：O(1)，只保存候选起点和累计油量。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明