題目： LeetCode - 134. Gas Station

題目說明

有一個環形的加油站點，車子的油箱容量無限，給兩個陣列分別代表兩個加油站間需要消耗的油量以及到加油站能補充的油量，求從哪個起點開始可以走完一圈，若無法走完則回傳 -1。

解題思路

貪心法，一開始先選 0 作為起點，接著往下走，curr 紀錄目前剩下的油量若是油量不夠到下一個點則選擇下一個點作為起點，同時記錄總獲得的油量及消耗的油量，結束時若是總油量大於等於 0 代表可以從 start 開始走能走完一圈。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int total{}, curr{}, start{};
        for(int i{}; i < gas.size(); ++i)
        {
            curr += gas[i] - cost[i];
            if(curr < 0) start = i + 1, curr = 0;
            total += gas[i] - cost[i];
        }
        return total >= 0 ? start : -1;
    }
};