134. 加油站

1. 题目简介

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

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

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

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

2. 问题分析

如果加油站的总油量小于待消耗的油量，那么可以直接返回 -1。否则一定能够行驶完全程。

假设汽车从 i 号加油站出发，当前油量 totalTank。为了保证能够开到 i + 1 号加油站，必须满足：

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

由此条件引申，如果汽车从 i 加油站出发，行驶到 j 号加油站时，剩余油量无法行驶到 j + 1 号加油站。那么从 i 到 j 之间的加油站出发，都无法行驶到 j + 1 号加油站。

为了找到可以经过所有加油站的起始点，可以遍历所有的加油站。遍历时可以根据上述条件进行优化。如果行驶到某一个加油站 i 时，无法继续行驶，那么下次遍历起点将为 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)