剑指 Offer II 038. 每日温度（单调栈）

文章目录

• 题目
• 一、单调栈

---

题目

请根据每日 气温 列表 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/iIQa4I

---

一、单调栈

解题思路：

维护一个存储下标的单调栈，其栈顶 —》栈底对应的温度由低 —》高。

正向遍历温度数组

• 当栈为空时，把temperatures[i]压入栈
• 当栈顶下标对应的温度 大于 temperatures[i] ，把temperatures[i]压入栈（维护单调栈 顶 - 底 —> 低 - 高）
• 当栈顶下标对应的温度 小于 temperatures[i] ，把栈顶下标d出，当前下标 i 减 栈顶下标 即为 栈顶下标 对应的等待的天数，存储进数组res[栈顶下标] 。(重复此 *** 作至条件不满足)

代码如下：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> eq = new LinkedList<>();
        int n = temperatures.length;
        int[] res =new int[n];
        for(int i=0;i<n;i++){
            //eq,peek是下标
            while(!eq.isEmpty()&&temperatures[eq.peek()]<temperatures[i]){
                int index = eq.pop();
                res[index] = i-index;
            }
            eq.push(i);
        }
        return res;
    }
}

加深栈方法使用：
剑指 Offer II 037. 小行星碰撞（栈）
剑指 Offer II 036. 后缀表达式(栈)

---

解析参考力扣：
https://leetcode-cn.com/problems/iIQa4I/solution/mei-ri-wen-du-by-leetcode-solution-vh9j/

侵删