題目網址: https://leetcode.cn/problems/car-fleet/

題意: 在一條單行道上, 有 n 輛車開往同一目的地, 目的地是幾英里外的 target。

給兩個整數 array position、speed, 其中 position[i] 是第 i 輛車的位置, speed[i] 是第 i 輛車的時速(英里/小時)。

一輛車永遠不會超過前面的另一輛車, 但它可以追上去, 並與前車以相同的速度緊接著行駛。此時, 我們可忽略這兩輛車之間的距離, 也就是說, 它們被假定處於相同的位置。

車隊是一些由行駛在相同位置、具有相同速度的車組成的非空集合。注意, 一輛車也可以是一個車隊。

即便一輛車在目的地才趕上了一個車隊, 它們仍然會被視作是同一個車隊。

返回到達目的地的車隊數量。

Solution：

想法：利用 Monotonic（遞減） Stack, 先使用 map 根據 position[i] 「由小到大」排序, 然後依序取出, 並計算 position[i] 到 target 所需的時間。如果當前所需的時間 time ≥ stk.top(), 則代表兩車會合併為一個車隊, 因為離 target 較遠的那輛車所需的時間 stk.top() 較短, 但是道路為單向且不能超車。所以最後抵達 target 的時間會受制於 time。所以一旦 time ≥ stk.top() 就要 stk.pop(), 將兩輛車合併為一個車隊（受限於當前 time 的車隊）, 直到 stk.top() > time, 才能將 time push 到 stk 中。最後, stk 中的元素個數即為車隊數量。

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        map<int, int> ps;
        for (int i = 0; i < position.size(); ++i) {
            ps[position[i]] = speed[i];
        }

        stack<float> stk;
        for (auto& [pos, spd] : ps) {
            const float time = float(target - pos) / spd;
            while (!stk.empty() && time >= stk.top()) {
                stk.pop();
            }
            stk.emplace(time);
        }
        return stk.size();
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ stk 中的元素個數不超過 n