今天繼續加深「單調堆疊」的概念

739. Daily Temperatures
題目
給一個表示每日溫度整數陣列，其中answer[i]是在第i天之後您必須等待的天數才能獲得較溫暖的溫度。如果未來沒有一天可以這樣做，則保留 answer[i] == 0。

想法:
使用單調遞減堆疊 (堆疊頂部的值最小，底部最大)，存放於 stack 裡的值都是還尚寫入結果的，倘若預到天氣的比 stack 裡的所有天的天氣都還要熱，就一一將較冷的天數從 stack 中彈出，再計算與當前天數的差值後，寫入結果陣列裡。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size(); 
        stack<pair<int, int>> st; // temperature, index
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            int v = temperatures[i];
            while (!st.empty() && v > st.top().first) {
                pair<int, int> p = st.top();
                st.pop();
                res[p.second] = i - p.second;
            }
            st.push({v, i});
        }
        
        return res;
    }
};

時間複雜度: O(N)