LeetCode739 每日温度

Ted

发布于：2020年12月25日

次浏览

第一次学习使用神奇的单调栈方法解每日温度问题。

739. 每日温度

题目描述

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

题目解析

这道题开始看到题后我毫无头绪，除了用暴力解以外也完全想不出什么好办法，之前看过了好多遍，连看答案都看不太明白，也没能真正下手开始做。今天在学习leetbook中的“栈”部分时候再次遇到了这道题，决定认真学习一下。

题目官方解析的暴力法完全看不懂，各种数组套来套去不知道在说什么，故直接跳转到第二个方法————单调栈。单调栈法的文字部分也看不太懂，可是有例子就非常容易搞明白了。看了看例子，大概的思想是维护一个单调递减的栈，由于我们要找到每一个温度后面的第一个更高的温度，所以当后面温度是递减或相等的时候就把它们压入栈中保存。

如果我们遇到了比栈顶元素更高的值，那么可以有两种情况：

该值比栈中的所有元素都要大，将所有元素依次出栈后将该值压栈。
该值比栈中部分元素大，将该部分元素依次出栈后将该值压栈。

由于我们在栈中保存了之前单调递减的所有元素，所以我们可以以这些元素为依据来求出题目中要求的第一个更高的气温。我们可以用官方答案的例子作为参考。具体实现可以参考如下代码。

代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int>s;                    //s保存所有的温度值
        stack<int>index;                //index保存所有的索引值，与s栈保持一致
        vector<int>result(T.size(), -1);//全部初始化为-1
        for(int i = 0; i < T.size(); i++){
            if(s.empty()){
                s.push(T[i]);
                index.push(i);
            }
            if(T[i] > s.top()){
                while(!s.empty()){
                    if(T[i] > s.top()){
                        s.pop();
                        result[index.top()] = i - index.top();
                        index.pop();
                    }  
                    else{
                        s.push(T[i]);
                        index.push(i);
                        break;
                    }                  
                }
                if(s.empty()){
                    s.push(T[i]);
                    index.push(i);
                }
            }
            else{
                s.push(T[i]);
                index.push(i);
            }
        }
        if(!s.empty()){
            while(!s.empty()){
                s.pop();
                result[index.top()] = 0;
                index.pop();                
            }
        }
        return result;
    }
};

最开始写的代码，按照我初始的逻辑写好的，又臭又长，中间有好多重复的部分可以优化。首先定义两个栈s和index，分别保存温度值和温度值对应的数组索引值，并初始化一个大小为n的数组result保存所有的结果。

代码运行时，首先对于每一个温度值进行判断，如果栈为空或该值小于栈顶值就将其加入栈中，如果大于栈顶元素时，根据上文说过的逻辑进行操作。将栈顶元素出栈，并在result数组中计算两个温度值对应索引的差值。然后再继续进行判断该值与下一个栈顶元素值的大小。

可以看到该代码中有太多重复的部分，完全可以将压栈的部分放到一起，于是进行修改之后可以得到如下代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int>index;
        vector<int>result(T.size(), 0);//全部初始化为0,最后不用再加上处理步骤
        for(int i = 0; i < T.size(); i++){            
            while(!index.empty() && T[i] > T[index.top()]){
                result[index.top()] = i - index.top();
                index.pop();
            }
            index.push(i);            
        }
        return result;
    }
};