[Day 20] Leetcode 739. Daily Temperatures (C++)

前言

今天来个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找到更多相关题目。