2022-1-11 739. 每日温度（单调栈）

本文主要是介绍2022-1-11 739. 每日温度（单调栈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注：

题目：
请根据每日气温列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

题解：
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

例如本题其实就是找找到一个元素右边第一个比自己大的元素。此时就应该想到用单调栈。

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素的元素，优点是只需要遍历一次。

在使用单调栈的时候首先要明确如下两点：
（1）单调栈里存放的元素是什么？
单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。

（2）单调栈里元素是递增呢？还是递减呢？
注意一下顺序为从栈头到栈底的顺序，因为单纯的说从左到右或者从前到后，不说栈头朝哪个方向的话，大家一定会越看越懵。这里我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，加入一个元素i，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

使用单调栈主要有三个判断条件。

当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

把这三种情况分析清楚了，也就理解透彻了。

对于本题来说：

当前遍历的元素T[i]小于栈顶元素T[st.top()]时，将当前元素压入栈中。
当前遍历的元素T[i]等于栈顶元素T[st.top()]时，也将当前元素压入栈中。
当前遍历的元素T[i]大于栈顶元素T[st.top()]时，将栈顶元素弹出，直到栈顶元素大于或等于当前遍历的元素，或者直到栈为空。

复杂度分析
时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。

空间复杂度：O(n)，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(),0);if(temperatures.size()==0||temperatures.size()==1){return result;}stack<int> st;st.push(0);for(int i=1;i<temperatures.size();i++){if(temperatures[i]<=temperatures[st.top()]){st.push(i);}else{while(!st.empty()&&temperatures[i]>temperatures[st.top()]){result[st.top()]=i-st.top();st.pop();}st.push(i);}}return result;}
};