739.每日温度

发表于： 分类于：
字数： 1188 阅读：≈ 3分钟

🌡️ 739.每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，在该位置用 0 来代替。

思路

基本思想

要与后面的数进行比较，然后结果传递给前面的数，所以第一想法就是暴力法，判断对于当前元素来说，下一个比他大的元素出现在后面的第几个位置，这样统计最终得到结果，暴力法的代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(),0);
        for(int i=0;i<temperatures.size();++i){
            int index=0;
            //从当前元素开始找
            for(int j=i;j<temperatures.size();++j){
                //当前元素不比第i个元素大，就继续找
                if(temperatures[j]<=temperatures[i]){
                    ++index;
                }else{//找到比第i个元素大的元素
                    ans[i]=index;
                    break;//退出当前循环
                }
            }
            //内层for循环结束都没有找到比第i个元素大的，就不更新
            //此时ans为0
        }
        return ans;
    }
};

当测试用例过长时，程序运行超时

像这种寻找一个元素的左边或者右边，第一个比自己大或者比自己小的元素的位置，可以使用单调栈

单调栈有两个注意的点：

  1. 栈中存放的是元素的下标，这样取元素时直接拿着下标去原数组中找即可
  2. 栈中的元素从栈顶到栈底需要满足一定的条件，递增或递减

知道这两点之后，在具体情况具体分析

本题中，求的是第i个元素的右边第一个比自己大的元素，也就是说比较小的元素都不统计，所以单调栈的栈顶到栈底的元素需要递增，这样满足第i个元素后面的元素全是小于等于自己的

一旦出现大于自己的元素，就说明找到了第一个大于自己的元素，可以用下标相减的方式来计算这个元素隔了几个位置，总结来说有三种情况：

  1. 当前元素小于栈顶元素，直接入栈

  2. 当前元素等于栈顶元素，直接入栈

  3. 当前元素大于栈顶元素，栈顶元素找到第一个比他大的元素，出栈并得出结果

    当前元素入栈时需要保证小于栈顶元素

当一个元素遍历到结束还没有发现比他大的元素，说明当前元素后面的元素都不大于它，此时这个元素的位置结果应该是0，所以结果数组应该全部初始化为0

执行流程

  1. 初始化结果数组全为0
  2. 遍历数组，当前元素不大于栈顶元素，直接入栈，大于栈顶元素就需要将大于的栈顶元素全部出栈，出栈过程中栈顶元素就可以计算结果
  3. 返回最终结果数组

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(),0);
        stack<int> s;
        s.push(0);//第一个元素入栈
        for(int i=1;i<temperatures.size();++i){
            //当前元素小于等于栈顶元素，直接入栈
            if(temperatures[i]<=temperatures[s.top()]){
                s.push(i);
            }else{//当前元素大于栈顶元素
                //想要入栈需要找到第一个大于当前元素的位置
                while(!s.empty()&&temperatures[i]>temperatures[s.top()]){
                    ans[s.top()]=i-s.top();
                    s.pop();
                }
                s.push(i);
            }
        }
        return ans;
    }
};

总结

暴力法思路是对的，但是遇到大的测试用例就会超时，单调栈记录了栈顶到栈底递增的序列，一旦出现一个大于的数字，就说明栈中的一些元素找到了第一个比自己大的元素，就这样保持栈顶到栈底递增的规则一直遍历，就可以得到最终的结果

就是在容器中元素的遍历过程中加上了判断条件，始终保持单调栈中元素的递减，一旦出现递增的元素，说明栈中的一部分元素找到了第一个更大的温度，此时这些元素对应的结果就可以计算出来