題目網址：https://leetcode.cn/problems/gas-station/

題意：在一條環路上有 n 個加油站, 其中第 i 個加油站有汽油 gas[i] 升。

你有一輛油箱容量無限的的汽車, 從第 i 個加油站開往第 i + 1 個加油站需要消耗 cost[i] 升汽油。你從其中的一個加油站出發, 開始時油箱為空。

給定兩個整數 array gas 和 cost, 如果可以繞環路行駛一圈, 則返回出發時加油站的 index, 否則返回 -1。如果存在解, 則保證它是唯一的。

Solution：

想法：利用 Greedy, 首先判斷總油量是否小於總消耗量。如果是, 那肯定不能走完一圈。否則, 肯定能走完一圈。接下來就是遍歷 nums, 從第一站開始, 計算每一站剩餘的油量, 如果當走到第 i 站時油量為負, 則以第 i + 1 站作為起點重新計算。若抵達某一站時油量為負, 說明從起點到該站中間的所有站都不能到達該點

e.g. gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] (見下圖)

  • 假設從 i = 4 出發, 此時的 gas[i] = 5, cost[i] = 2

    • i = 4 做完, 此時 curGas = 5 - 2 = 3 ≥ 0
    • i = 0 做完, 此時 curGas = 3 + 1 - 3 = 1 ≥ 0
    • i = 1 做完, 此時 curGas = 1 + 2 - 4 = -1 < 0

    ➔ 下一輪會從 i = 2 重新計算, 因為以 i = 4、0、1 為起點都無法抵達 i = 2

    • 這是因為以 i = 4 為起點出發, 抵達 i = 0 時的油量必須 ≥ 0 才行
    • 若直接以 i = 0 為起點出發, 則起始油量會為 0
      ➔ 等同從上一站抵達 i = 0 時的剩餘油量 = 0 ( ≥ 0 中的 worse case)
    • 若從 i = 4 都無法抵達 i = 2, 則從 i = 0、1 更不可能抵達。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // 總油量 < 總消耗量, 肯定無法走完一圈
        if (sum(gas) < sum(cost)) {
            return -1;
        }

        int res = 0, curGas = 0;
        for (int i = 0; i < gas.size(); ++i) {
            curGas += (gas[i] - cost[i]);

            if (curGas < 0) { // 若抵達第 i 站時油量 < 0, 則以第 (i + 1) 站為起點重新計算
                curGas = 0;
                res = i + 1;
            }
        }
        return res;
    }

private:
    int sum(const vector<int>& nums){
        return accumulate(nums.begin(), nums.end(), 0);
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間