739. 每日溫度

思路

遍歷整個數組，並將溫度放到棧中，拿當前的溫度去跟棧中的溫度比較，
假如比較高，就表示棧中元素遇到了一個比自己高的溫度，也就找到了「棧中元素的答案」。

對於當前元素來說，它會不斷的跟棧頂比較大小，最後將自己放入棧中。
每一個元素都這樣做，因此棧本身是嚴格單調遞增的，
後來的元素試著將會將前面的元素淘汰，淘汰成功，被淘汰的元素就找到了答案。

程式碼

單調棧

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> stk;
        for(int i = 0; i < n; ++i) {
            // 只要棧不空，且當前元素比棧頂元素大，就彈出棧頂元素，並更新答案。
            while(!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
                temperatures[stk.top()] = i - stk.top(); // 天數 = 當前索引 - 棧頂索引
                stk.pop(); // 彈出棧頂元素
            }
            stk.push(i); // 將當前元素放入棧中
        }
        // 棧中剩下的元素，表示沒有比自己高的溫度，所以答案為 0。
        while(!stk.empty()) {
            temperatures[stk.top()] = 0;
            stk.pop();
        }
        return temperatures;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$