14.加油站

题目

在一条环路上有 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 + 5 = 8 升汽油
  • 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
  • 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
  • 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
  • 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。

因此，3 可为起始索引。

示例 2:

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

因此，无论怎样，你都不可能绕环路行驶一周。

提示:

• n == gas.length == cost.length
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104
• 输入保证答案唯一。

思路

• 题目有一点很重要： 如果存在解，则 保证 它是 唯一 的。

• 能跑一圈的前提有两个:

  • 每一站的油量都能达到下一站
  • 一圈下来剩下的油量是大于等于0的

• 我们首先检查第 0 个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        start = 0
        while start < n:
            cur = 0
            step = 0
            while step < n:
                nex = (start + step) % n
                cur += gas[nex] - cost[nex]
                # 走到这一步的时候当前的油量< 0了。需要更新起始的站，重新从下一站开始来计算了
                if cur < 0:
                    break
                # 走下一步    
                step += 1
            # 走了n步，也就是一圈了
            if step == n:
                return start
            else:
                # 没走了，一圈，从当前已经走的步数继续遍历找
                start = start + step + 1
        return -1

注意: 为什么使用 start += step + 1 而不是 start += 1？

​如果从起点 start 出发，在走了 step 步后失败（无法到达第 step+1 个加油站），那么从 start 到 start+step 之间的任意一个加油站作为新起点都一定会失败。 对于任意k在[start + 1, start + step]:

• 如果从 k 出发，我们失去了 start → k 这段路的油量积累（由问题性质决定）。
• 由于 start → k 这段的油量积累 ​必然是非负的​（因为如果这段是负的，那在 k 之前就已经失败了）。
• 因此，当从 k 开始时，油量比从 start 开始更少，不可能完成接下来的路程。

使用 start += step + 1 是基于数学性质的优化，避免了无效的重复检查。 改为 start += 1 虽然逻辑正确，但会退化为 O(n²) 的暴力解法，在大型数据集上效率极低。

复杂度分析:

• 时间复杂度：O(N)，其中 N 为数组的长度。我们对数组进行了单次遍历。

• 空间复杂度：O(1)。

方法二

允许油量为负，但是总剩余油量应该大于等于0，否则不存在解的。

存在解的情况下，利用贪心法的思想，找到最低点，它的下一个点出发的话，可以保证前期得到剩余油量最大，所以可以跑完全程。

public int canCompleteCircuit2(int[] gas, int[] cost) {
    // 一圈下来的总剩余油量
    int totalNum = 0;
    // 从某一站开始时每一站剩余的油量
    int curNum = 0;
    int idx = 0;

    for (int i = 0; i < gas.length; i++) {
        curNum += gas[i] - cost[i];
        totalNum += gas[i] - cost[i];
        if (curNum < 0) {
            idx = (i+1) % gas.length;
            curNum = 0;
        }

    }

    if(totalNum < 0) return -1;
    return idx;
}

class Solution {
    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        var total = 0
        var current = 0
        var index = 0

        for (i in gas.indices) {
            current += gas[i] - cost[i]
            total += gas[i] - cost[i]
            if (current < 0) {
                index = i + 1
                current = 0 // 注意，重新开始算起点了，所以必须要把current重置为0
            }
        }
        if (total < 0) {
            return -1
        }

        return index
    }
}

解释

为什么 idx = i + 1

核心逻辑：如果从 idx 出发，走到第 i 站时油量为负，说明 idx 到 i 之间的任何一站都不能作为起点。

原因：从 idx 出发时油量是 0，途中每一站到达时油量都是非负的（否则上一次就已经重置了）。如果从中间某站 k（idx ≤ k ≤ i）出发，到达第 i 站的油量 = 从 idx 出发到第 i 站的油量 - 从 idx 出发到第 k 站的油量，后半部分 ≥ 0，所以结果只会更差。

因此直接跳过，从 i + 1 重新尝试。

为什么要 % gas.length

只是防止最后一站（i = gas.length - 1）时 i + 1 越界。

实际上 totalNum < 0 已经处理了无解的情况，有解时 idx 不会真的等于 gas.length，所以 % gas.length 只是防御性写法，去掉也不影响正确性。

• 下一篇

• 邮箱 ：charon.chui@gmail.com
• Good Luck!