739. Daily Temperatures

題目網址: https://leetcode.cn/problems/daily-temperatures/

題意: 給一整數 array temperatures 代表每天的溫度。請返回 array res, 其中 res[i] 是指對於第 i 天, 下一個更高溫度是出現在幾天後。如果氣溫在這之後都不會升高, 則該位置用 0 來代替。

Solution：

想法：利用 Stack, 使用 Monotonic（遞減） Stack stk 紀錄 {temperature, idx}, 一旦當前溫度 temperatures[i] 比 stk.top().first 還高, 則不斷將 stk.top() 取出, 並計算 res[idx], 直到 stk.top().first > temperatures[i] 才把 temperatures[i] push 到 stk 中

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        const int n = temperatures.size();
        vector<int> res(n, 0); // 若最後 stk 不為空, 則剩餘元素的 res[idx] 皆為 0
        stack<pair<int, int>> stk; // {temperature, idx}

        for (int i = 0; i < n; ++i) {
            // 一旦當前溫度 > top, 則不斷將 top 給 pop 掉, 並計算 res[idx]
            while (!stk.empty() && temperatures[i] > stk.top().first) {
                auto [temperature, idx] = stk.top();
                stk.pop();
                res[idx] = i - idx;
            }
            stk.emplace(pair<int, int>{temperatures[i], i}); // push 當前元素
        }
        return res;
    }
};

• time：$O(n)$ ➔ for loop
• space：$O(n)$ ➔ stk 中的元素個數不超過 n