前言

今天來個top 100 liked中有趣的問題─739. Daily Temperatures，他相關的tags有：array、stack、monotonic stack，也算是經典的問題。

想法

題目的要求是希望每一天可以找到幾天後會有比他溫度還高的氣溫。
看到題目會有什麼想法呢？我看到題目的第一個想法是要從尾巴開始遍歷，為什麼？因為在算每一天的時候我們需要知道後面的資料，而如果從前面先記再去後面比對的話等於後面每一天都需要重新計算比對一次，想來還是先記錄後面的氣溫會比較合理。
那從後面開始遍歷要記錄什麼呢？最後一天的答案肯定是0，因為再後面就沒有氣溫了，當天的氣溫當然要保留下來，以便前面去比對；是第幾天應該也要保留，這樣前面才知道間隔了幾天；那倒數第二天的時候要做什麼呢？
第一種情況是氣溫<剛剛紀錄的最後一天，那就可以得到答案=1，而當天的氣溫跟日期也要記錄，因為前面可能也有比較低的日子需要這天的資料。
第二種情況是>=剛剛紀錄的最後一天的氣溫，那答案會=0，因為後面沒有更高的日子了，同樣當天的氣溫跟日期也要記錄，理由同上，因為前面可能也有比較低的日子需要這天的資料；但還有一件重要的事情，最後一天的資料可以刪掉了！
為什麼？因為既然我們前面出現了氣溫更高又更靠前的日子，前面的日子就絕對不需要後面那天的資料了！因為它既更高溫、又更早，那前面的日子在找更高溫的第一天時，找到那天就會找到答案了！
從中我們可以推論出一個規則─我們需要保留的日子資料，只有一連串氣溫由高到低，日子由後往前的資料，而這就是monotonic stack的概念，我們只需要保留同方向成長的stack。
那接下來我們要怎麼運用這個概念來解題呢？
假設現在的天氣資料如題目範例1是：[73,74,75,71,69,72,76,73]，按照前面的邏輯，從最後一天來，我們的氣溫stack是空的，因此73進去後發現沒有人比較高，stack存入(73,7)(氣溫,day)；
倒數第二天進去，發現第一個比它小，73<76，於是把(73,7)這組pop掉，繼續找發現沒了，答案填入0，並把(75,6)存入；
倒數第三天進去，馬上發現更高的，答案依據(75,6)的6減去5(day)，答案得到1，並把(72,5)存入，現在stack的狀態是((75,6),(72,5))；
倒數第四天進去，因為是stack，filo的概念，從後面開始檢查，也是第一個發現就更高，答案依據(72,5)的5減去4，得到1，並把(69,4)存入，現在stack的狀態是((75,6),(72,5),(69,4))；
倒數第五天進去，第一個碰到(69,4)發現沒有比今天高，pop掉；繼續看到(72,5)，發現比今天高，於是依據(72,5)的5減去3，得到2，並把(71,3)存入，現在stack的狀態是((75,6),(72,5),(71,3))；
...
按照這個邏輯，就可以把程式碼寫出來了。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // stack of higher temperatures
        stack<pair<int, int>> higherTemp;
		vector<int> ans(temperatures.size(),0);
		// start from the last day
        for (int i=temperatures.size()-1; i>=0; --i)
        {
            // check the stack until empty or find the higher temperature
            while(!higherTemp.empty() && higherTemp.top().first<=temperatures[i]){
                higherTemp.pop();
            }
            // if there are higher days, update the answer; otherwise, remain 0
            if(!higherTemp.empty()){
                ans[i] = higherTemp.top().second-i;
            }
            // push the current status
            higherTemp.push({temperatures[i],i});
        }
        
        return ans;
    }
};

比較值得注意的是時間複雜度的部分，會是O(n)。你可能會覺得怪怪的，我遍歷需要O(n)，每次檢查stack的時候應該也需要O(n)，相乘不是O(n^2)嗎?? 但事實上你每檢查一個，不是pop掉就是把東西塞進去，每個元素不會被重複檢查！只要一次不合格，就是pop掉;可以舉兩個極端的例子，一個是氣溫為1,2,3,4,5，那下場就是每次檢查到stack的第一個就找到答案，因此O(n)遍歷而每次只要檢查一次，是O(n)；而另一個氣溫是5,4,3,2,1，下場則是每次都會pop掉前面的答案，stack永遠只有一個東西，因此也是O(n)。
簡單來說，每個元素只會被加入一次跟pop一次，因此是O(n)。

結語

這類monotonic stack的問題也有系列問題，可以再延伸下去做，參考官方下面提到的similar questions有這些：

• Next Greater Element I
• Online Stock Span
  或可以在problems那邊選擇monotonic stack的tag找到更多相關題目。