【LeetCode 面试经典150题】134. Gas Station 加油站

134. Gas Station

题目大意

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

中文释义

沿着一条环形路线有 n 个加油站，第 i 个加油站有 gas[i] 单位的汽油。

你有一辆油箱无限的汽车，从第 i 个加油站到下一个（即第 i + 1 个）加油站需要消耗 cost[i] 单位的汽油。你从一个加油站开始旅行时油箱为空。

给定两个整数数组 gas 和 cost，如果你能顺时针方向绕环形路线走一圈，则返回起始加油站的索引，否则返回 -1。如果存在解决方案，它保证是唯一的。

Example

Example 1:

• Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
• Output: 3
• Explanation:
  • 从加油站 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 作为起始索引。

Example 2:

• Input: gas = [2,3,4], cost = [3,4,3]
• Output: -1
• Explanation:
  • 你不能从加油站 0 或 1 开始，因为没有足够的汽油到达下一个加油站。
  • 让我们从加油站 2 开始，加满 4 单位的汽油。你的油箱 = 0 + 4 = 4
  • 行驶到加油站 0。你的油箱 = 4 - 3 + 2 = 3
  • 行驶到加油站 1。你的油箱 = 3 - 3 + 3 = 3
  • 你无法回到加油站 2，因为需要 4 单位的汽油但你只有 3 单位。
  • 因此，无论你从哪里开始，你都不能绕一圈。

Constraints

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

解题思路

算法描述

这段代码的目的是找出能够绕环形路线走一圈的起始加油站索引。

- 首先，我们需要判断总油量是否大于等于总消耗量，这个条件等价于 是否存在一个加油站可以作为起点驾驶一圈。

• 如果以上条件满足，说明 一定存在一个加油站作为起点可以驾驶一圈，我们可以逐个排除。

• 举个例子，假设存在1-4这四个加油站，如果以1为起点，开始遍历，结果发现在3号加油站无法到达4号加油站，说明1、2、3号加油站都不能作为起点。

  • 这里需要仔细思考：
  • 以1号为起点如果到达2号，肯定会带来 （大于等于0 的额外汽油 + 2号加油站拥有的汽油）。
  • 以2号为起点，只能加上2号加油站拥有的汽油。
  • 因此，如果以1号为起点都不能到达之后的加油站，那么以2号为起点这种情况肯定也到不了。

• 用以上的方法进行遍历排除所有无法驾驶一圈的加油站起点，最终剩下的就是满足题意得起点加油站。

算法的关键步骤如下：

1. 计算总油量和总消耗:

   • 首先，使用 accumulate 函数计算所有加油站的总油量 (totalGas) 和总消耗 (totalCost)。
   • 如果总消耗大于总油量，说明无法完成整个环路，返回 -1。

2. 遍历加油站:

   • 初始化一个变量 start 为0，表示可能的起始加油站索引。
   • 初始化一个变量 currentGas 为0，表示当前油量。
   • 遍历所有加油站，对于每个加油站：
     • 更新 currentGas 为当前加油站提供的油量减去到下一个加油站的消耗。
     • 如果 currentGas 变为负数，说明从 start 到当前加油站的任何一个都不可能作为起始加油站，因此将 start 设置为 i + 1（下一个加油站的索引），并重置 currentGas。

3. 返回结果:

   • 遍历结束后，start 存储的是能够完成整个环路的起始加油站索引。

代码实现

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalGas = accumulate(gas.begin(), gas.end(), 0);
        int totalCost = accumulate(cost.begin(), cost.end(), 0);
        if (totalCost > totalGas) return -1;

        int start = 0, currentGas = 0;
        for (int i = 0; i < gas.size(); i++) {
            currentGas += gas[i] - cost[i];
            if (currentGas < 0) {
                start = i + 1;
                currentGas = 0;
            }
        }
        return start;
    }
};