跳转至

739. 每日温度

力扣链接(中等)：https://leetcode.cn/problems/daily-temperatures

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

个人题解

对于一维数组，如果要寻找任意一个元素的左边或者右边第一个比自己大或者比自己小的元素位置，此时通常考虑单调栈。

栈的特点是后进先出，假设我们要找右边第一个比当前元素大的元素位置，那么可以利用栈的特性来处理，使得栈中的元素一定是单调递增的，这样遍历一遍数组即可得到结果。

具体流程：首先将数组第一个元素下标入栈，然后从第二元素开始遍历数组，如果当前遍历的元素比栈顶元素大，则找到了第一个比栈顶元素大的元素，那么为了满足栈的单调性，就应该将栈顶元素出栈，同时将当前下标与栈顶元素值之差作为栈顶元素的结果，最后再将当前元素的下标入栈，等待下一次循环寻找第一个比自己大的元素。

C++
 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
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size(), 0);
        // 单调栈存储对应元素的下标
        stack<int> st;
        // 由于 1 <= temperatures.length，所以直接将第一个元素入栈
        st.push(0);

        for(int i = 1; i < temperatures.size(); i++) {
            // 当前元素大于前一个元素时，更新前一个元素的 result，并且将其出栈
            // 代表前一个元素已经找到下一个更大元素的位置，如果其 result 到最后也没更新
            // 代表后面没有元素比它大，那么其 result 就为初始值 0
            while(!st.empty() && temperatures[st.top()] < temperatures[i]) {
                // 注意这里是距离
                result[st.top()] = i - st.top();
                st.pop();
            }
            // 将当前元素入栈，作为下一个待处理元素
            st.push(i);
        }

        return result;
    }
};