01 每日温度 单调栈

739. 每日温度

已解答

中等

相关标签

相关企业

提示

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 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

---

// 版本一
class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {// 递增栈stack<int> st;vector<int> result(T.size(), 0);st.push(0);for (int i = 1; i < T.size(); i++) {if (T[i] < T[st.top()]) {                       // 情况一st.push(i);} else if (T[i] == T[st.top()]) {               // 情况二st.push(i);} else {while (!st.empty() && T[i] > T[st.top()]) { // 情况三result[st.top()] = i - st.top();st.pop();}st.push(i);}}return result;}
};

单调栈的适用场景

• 求当前元素左面或者右面第一个比当前元素大或者小的元素（位置和数值）都适合用单调栈来解决

本题思路（ O(n) ）

• 单调栈里面不要存元素，要存下标，直接存元素（要求的是距离，元素还有重复的不行）

• 如何比较大小

• 维护单调递增（从栈顶到栈底依次增大）（求的是当前元素的前面或者后面比这个元素大的元素）和单调递减（求的就是当前元素前面或者后面第一个比它小的元素的位置）

• 单调栈在本题的作用：存放遍历过的元素

  三种情况

• 当当前元素小于或者等于栈顶元素时，直接加入到栈中（维护的是单调递增）

• 本题要求是求比当前元素大的元素，而不是大于等于，所以等于时依然直接加入到栈中

• 若是当前元素大于栈顶元素，栈顶元素收获结果集（）并且弹出，然后继续和当前的栈顶元素（原来就在栈里面，栈顶元素后面的那个元素）比较大小，重复操作