# 2025 年「資訊科技產業專案設計」課程作業 4

## 134. Gas Station
> [LeetCode 134. Gas Station](https://leetcode.com/problems/gas-station/description/)

### 原始題意
There are `n` gas stations along a circular route, where the amount of gas at the `i-th` station is `gas[i]`.
You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `i-th` station to its next `(i + 1)` 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.

### 情境包裝
* **情境**：全球雲端服務的故障轉移路由測試 (Global Cloud Service Failover Routing Tests)。
* **細節**：
* 系統由 `n` 個邊緣區域 (Edge Regions) 組成一個邏輯環狀網路。
* 在區域 `i`，系統可以獲得 `g[i]` 個請求權杖 (Request Tokens)。
* 要將流量從區域 `i` 轉發到下一個區域 `(i+1) mod n`，系統必須消耗 `c[i]` 個請求權杖。
* **目標**：選擇一個起始區域進行演練，初始權杖為 0。若能完成一整圈回到起點且途中權杖餘額皆非負，回傳該起始索引；否則回傳 -1。

### 解法

#### Greedy (One Pass)
核心概念：如果總獲得權杖數小於總消耗，則無法繞一圈。若大於等於 0，則必然有解。利用貪婪演算法，當局部餘額小於 0 時，代表目前的起點無效，直接將起點重置為下一個位置。

#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& budget, vector<int>& cost) {
        long long total = 0;      // Global sum of diff
        long long balance = 0;    // Sum of diff from 'start' to current i
        int start = 0;

        for (int i = 0; i < (int)budget.size(); ++i) {
            long long diff = (long long)budget[i] - cost[i];
            total += diff;
            balance += diff;

            // Fail on segment start..i => skip all starts in [start..i]
            // Because starting from any k in [start, i] would still result in negative balance at i
            if (balance < 0) {
                start = i + 1;
                balance = 0;
            }
        }
        return (total < 0) ? -1 : start;
    }
};

### Follow up

#### 1. Return ALL valid starting region indices

如果題目移除了「唯一解」的保證，並要求回傳所有可能的起始點：

* **策略**：使用 **Prefix Sum + Monotonic Queue (Sliding Window Minimum)**。
* **實作思路**：
* 將陣列長度加倍 `(2n)` 以處理環狀結構。
* 計算差值 `diff[i] = g[i] - c[i]` 的前綴和 。
* 有效的起始點 必須滿足：對於所有 ， 。
* 這等價於尋找區間內的最小值： 。
* 使用單調佇列 (Monotonic Deque) 維護大小為 的滑動視窗最小值，即可在 時間內找出所有符合條件的 。

vector<int> getAllStartingStations(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    vector<int> res;

    // 1. Construct doubled difference array & Prefix Sum
    // P[i] stores the cumulative sum of diff from 0 to i-1
    vector<long long> P(2 * n + 1, 0);
    for (int i = 0; i < 2 * n; ++i) {
        P[i + 1] = P[i] + (long long)(gas[i % n] - cost[i % n]);
    }

    // 2. Sliding Window Minimum using Monotonic Queue (Deque)
    // We need to check if min(P[s+1]...P[s+n]) >= P[s]
    deque<int> dq; // Stores indices of P, keeping P[dq] increasing

    // Iterate through the doubled array (representing the window end)
    for (int i = 1; i < 2 * n; ++i) {
        // Maintain monotonic property: remove elements larger than current P[i]
        while (!dq.empty() && P[dq.back()] >= P[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // Calculate corresponding start index 's'
        // If current window end is 'i', and window size is 'n', then start is 'i - n'
        if (i >= n) {
            int s = i - n;
            
            // Remove indices that are out of the current window (s, s+n]
            // Valid range for min search is [s+1, s+n]
            if (dq.front() <= s) {
                dq.pop_front();
            }

            // Check condition: min(window) >= P[s]
            if (s < n && P[dq.front()] >= P[s]) {
                res.push_back(s);
            }
        }
    }
    return res;
}

### 模擬面試問答

* **🟠Interviewer—題目敘述**
* Hi, welcome to the interview.
* You’re operating a global cloud service with `n` edge regions connected in a logical ring for failover routing tests.
* At region `i`, your system can “gain” `g[i]` request tokens. To forward traffic from region `i` to the next region `(i+1) mod n`, the system must “spend” `c[i]` request tokens.
* You may choose ANY region as the starting point for a failover drill. The drill starts with 0 request tokens.
* Return the starting region index that allows the system to complete a full loop and return to the start. If it is impossible, return -1.
* Assume that if a solution exists, it is unique. Any questions?
* **👩‍💻Interviewee—確認限制 (Clarification)**
* Thanks. A few quick clarifications:
* Are `g[i]` and `c[i]` non-negative integers?
* What’s the expected constraint on `n`? For example, up to $10^5$?
* The routing path is fixed (`i` -> `(i+1) mod n`), no skipping regions, correct?
* **🟠Interviewer:**
* Correct on all. `n` can be up to $10^5$, and also we want an $O(N)$ solution.
* **👩‍💻Interviewee—舉例 (Sanity Check)**
* Let me use a classic example to trace the process.
* Suppose:
* `g = [1, 2, 3, 4, 5]` (tokens gained)
* `c = [3, 4, 5, 1, 2]` (tokens spent)
* First, I calculate the net difference `diff[i] = g[i] - c[i]`:
* `diff = [-2, -2, -2, +3, +3]`
* If I start at **index 0**:
* Current balance becomes `-2` immediately. **Fail.**
* If I start at **index 3** (where `diff` is positive):
* Step 1 (Region 3): Balance = `+3`. (OK)
* Step 2 (Region 4): Balance = `3 + 3 = 6`. (OK)
* Step 3 (Region 0): Balance = `6 + (-2) = 4`. (OK)
* Step 4 (Region 1): Balance = `4 + (-2) = 2`. (OK)
* Step 5 (Region 2): Balance = `2 + (-2) = 0`. (OK)
* Since the balance never drops below zero and we return to the start, **index 3** should be the valid starting point. Is that consistent?
* **🟠Interviewer:**
* Yes. And any edge cases?
* **👩‍💻Interviewee—邊界測試**
* All diff = 0: `total=0` and balance never drops below 0 => start remains 0, which is valid.
* Large values: Need to use `long long` for cumulative totals to avoid overflow.
* **🟠Interviewer:**
* What approach would you take?
* **👩‍💻Interviewee—解題思路**
* Brute force would try each starting region and simulate a full failover loop, which is $O(N^2)$ and too slow for $10^5$.
* I’ll use a **greedy one-pass approach** based on net token delta at each region: `diff[i] = g[i] - c[i]`.
* Two key observations:
1. If `total = sum(diff) < 0`, then total request tokens gained is less than required. No solution exists => return -1.
2. If `total >= 0`, then at least one solution exists.
* **One-pass algorithm**:
* Maintain `start` (candidate index) and `balance` (running sum from start).
* Scan `i` from `0` to `n-1`:
* `balance += diff[i]`
* If `balance < 0`: This means starting from `start`, we run out of tokens at `i`. Crucially, **NONE** of the regions in `[start..i]` can be a valid starting region.
* So we set `start = i + 1` and reset `balance = 0`.
* At the end, if `total < 0` return -1, else return `start`.
* **🟠Interviewer:**
* You claimed: when balance < 0 at i, none of the regions from start to i can be a valid start. Can you explain that precisely?
* **👩‍💻Interviewee—證明**
* Let $S(a,b)$ be the sum of diff from $a$ to $b$ inclusive.
* At the moment `balance < 0`, we have: $S(start, i) < 0$.
* Also, because we only reset start when balance first becomes negative, for any $k$ in `(start..i]`, the partial sum up to $k-1$ never went negative: $S(start, k-1) \ge 0$.
* Now consider starting at region $k$ and attempting to reach `i+1`. The net change is:
* $S(k, i) = S(start, i) - S(start, k-1)$
* Since $S(start, i) < 0$ and $S(start, k-1) \ge 0$, we get $S(k, i) < 0$.
* That means starting at $k$ would also run out of tokens before or at $i$, so $k$ cannot be valid. We can safely jump `start` to `i+1`.
* **🟠Interviewer:**
* **🟠Interviewer:**
* Great. Please implement it in C++.
* **👩‍💻Interviewee—實作**
* I'll use `long long` for `total` and `balance` to avoid overflow.
* (Implemented code as shown in the Solution section above)
* Time Complexity: $O(N)$, Space Complexity: $O(1)$.
* **🟠Interviewer:**
* Looks good. Please walk through the sample.
* **👩‍💻Interviewee—測試 (Dry Run)**
* Sample: `g = [1,2,3,4,5]`, `c = [3,4,5,1,2]`.
* `diff = [-2, -2, -2, +3, +3]`.
* **Iter 0 (i=0)**: `diff=-2`. `balance=-2`. Since balance < 0, reset `start=1`, `balance=0`.
* **Iter 1 (i=1)**: `diff=-2`. `balance=-2`. Since balance < 0, reset `start=2`, `balance=0`.
* **Iter 2 (i=2)**: `diff=-2`. `balance=-2`. Since balance < 0, reset `start=3`, `balance=0`.
* **Iter 3 (i=3)**: `diff=+3`. `balance=3`. Valid so far.
* **Iter 4 (i=4)**: `diff=+3`. `balance=6`. Valid so far.
* End loop. `total = -2-2-2+3+3 = 0`.
* Since `total >= 0`, return `start = 3`.
* Interpretation: Start the drill at region 3, and the balance never drops below 0.
* **🟠Interviewer:**
* Follow-up: remove the “unique solution” guarantee. Return ALL valid starting region indices. What would you do?
* **👩‍💻Interviewee—Follow up**
* If solutions may not be unique, the one-pass greedy isn’t enough.
* I’d use **Prefix Sum + Monotonic Queue**.
* Create a linearized array of length `2n` by repeating `diff`.
* Build prefix sums $P$. A starting region $s$ is valid if the sliding window minimum of $P$ in range $(s, s+n]$ is $\ge P[s]$.
* We can maintain a monotonic deque for the minimum prefix value within a window of size $n$.
* This allows us to collect all valid $s$ in $O(N)$ time and $O(N)$ space.
* **🟠Interviewer:**
* Great. That concludes the interview. Thanks!
* **👩‍💻Interviewee:**
* Thank you for your time.