4、每日温度

题目描述

每日温度

题目描述：

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1：

输入： temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

输出：arr = [1, 1, 4, 2, 1, 1, 0, 0]

示例 2：

输入：temperatures = [30,30,31,45,31,34,56]

输出：arr = [2,1,1,3,1,1,0]

题目解析

其实我们可以换种方式理解这个题目，比如我们 temperatures[0] = 30,则我们需要找到后面第一个比 30 大的数，也就是 31，31 的下标为 2，30 的下标为 0 ，则我们的返回数组 arr[0] = 2。

理解了题目之后我们来说一下解题思路。

遍历数组，数组中的值为待入栈元素，待入栈元素入栈时会先跟栈顶元素进行对比，如果小于该值则入栈，如果大于则将栈顶元素出栈，新的元素入栈。

例如栈顶为 69，新的元素为 72，则 69 出栈，72 入栈。并赋值给 arr，69 的索引为 4，72 的索引为 5，则 arr[4] = 5 - 4 = 1，这个题目用到的是单调栈的思想，下面我们来看一下视频解析。

注：栈中的括号内的值，代表索引对应的元素，我们的入栈的为索引值，为了便于理解将其对应的值写在了括号中

代码

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        if (len == 0) {
            return T;
        }
        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[len];
        int t = 0;
        for (int i = 0; i < len; i++) {
            //单调栈
            while (!stack.isEmpty() && T[i] > T[stack.peek()]){
                  arr[stack.peek()] = i - stack.pop();
            }
            stack.push(i);
        }
        return arr;

    }
}

C++：

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int len = T.size();
        // 边界情况：空数组直接返回
        if (len == 0) {
            return T;
        }
        
        stack<int> st; // 单调栈：存储温度数组的索引（栈中索引对应的温度单调递减）
        vector<int> arr(len, 0); // 结果数组，初始化为0（默认无更高温度）
        
        // 遍历每个温度的索引
        for (int i = 0; i < len; ++i) {
            // 核心逻辑：当当前温度 > 栈顶索引对应的温度时，计算天数差
            while (!st.empty() && T[i] > T[st.top()]) {
                int topIdx = st.top(); // 获取栈顶索引（C++栈pop无返回值，需先top再pop）
                arr[topIdx] = i - topIdx; // 天数差 = 当前索引 - 栈顶索引
                st.pop(); // 弹出栈顶（已找到更高温度）
            }
            // 当前索引入栈（维护单调递减特性）
            st.push(i);
        }
        
        return arr;
    }
};