739.每日温度

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

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

Solution

单调栈

  • 先进先出：记录的数据加在最上面，丢掉的数据也在最上面
  • 单调性：记录t[i]之前会把所有$\leq$t[i]的数据丢掉

因为题目要求是求天数(数据下标之差)，所以直接把序号入栈

从后往前

栈中记录下一个更大元素的「候选项」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;  // 获取温度数组的长度
        int[] ans = new int[n];  // 创建一个结果数组，存放每一天需要等待的天数
        Deque<Integer> st = new ArrayDeque<>();  // 创建一个栈，用于存放温度的索引
        
        // 从后向前遍历温度数组
        for (int i = n - 1; i >= 0; i--) {
            int t = temperatures[i];  // 当前温度
            
            // 如果栈不为空且当前温度大于等于栈顶索引对应的温度，则弹出栈顶索引
            while (!st.isEmpty() && t >= temperatures[st.peek()]) {
                st.pop();
            }
            
            // 如果栈不为空，说明存在比当前温度高的温度
            if (!st.isEmpty()) {
                ans[i] = st.peek() - i;  // 计算等待天数并存入结果数组
            }
            
            // 将当前索引入栈
            st.push(i);
        }
        
        return ans;  // 返回结果数组
    }
}

从前往后

栈中记录还没算出「下一个更大元素」的那些数（的下标）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;  // 获取温度数组的长度
        int[] ans = new int[n];  // 创建一个结果数组，存放每一天需要等待的天数
        Deque<Integer> st = new ArrayDeque<>();  // 创建一个栈，用于存放温度的索引
        
        // 从前向后遍历温度数组
        for (int i = 0; i < n; i++) {
            int t = temperatures[i];  // 当前温度
            
            // 当栈不为空且当前温度大于栈顶索引对应的温度时
            while (!st.isEmpty() && t > temperatures[st.peek()]) {
                int j = st.pop();  // 弹出栈顶索引
                ans[j] = i - j;  // 计算等待天数并存入结果数组
            }
            
            // 将当前索引入栈
            st.push(i);
        }
        
        return ans;  // 返回结果数组
    }
}