当前位置：首页 > article >正文

每日温度问题：如何高效解决？

article 2025/2/18 17:27:17

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

问题分析

我们需要计算每一天之后需要等多少天才能遇到更高的温度。如果无法找到更高的温度，就返回 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]

解题思路：使用单调栈

在这个问题中，我们要计算每个温度之后，需要多少天才会遇到一个更高的温度。一个直接的暴力解法是，对每一天，从它之后的所有天中查找第一个更高的温度，这样会导致 O(n^2) 的时间复杂度。显然，暴力解法并不高效，特别是对于较大的输入。

为了提高效率，我们可以使用一个单调栈来将时间复杂度降低到 O(n)。下面是具体的思路：

关键步骤：

从后向前遍历：我们从最后一天开始遍历，每次都试图通过栈来维护一个"待解决"的温度序列。这样可以更容易地通过栈找到每个温度的下一个更高温度。
维护递减栈：栈中存储的是当前遍历过的温度的索引，并且栈中的温度是递减的。这意味着栈顶的元素对应的温度是当前栈中最小的（即当前最可能成为下一个更高温度的温度）。
遇到更高温度时计算天数：如果栈顶元素的温度比当前温度低，我们就可以计算该元素的下一个更高温度的天数。
栈顶小于等于当前温度时，出栈：如果栈顶的温度小于当前温度，那么说明当前温度是下一个更高温度的候选，因此栈顶元素出栈，继续判断下一个栈顶元素。
栈顶大于当前温度时，计算等待天数：栈顶元素的温度大于当前温度时，说明找到了下一个更高的温度，计算距离当前天数的差。
压入当前索引：最后，将当前温度的索引压入栈中，准备处理下一个温度。

代码实现：

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;  // 返回结果数组
    }
}

代码详解：

栈的作用：栈存储的是温度的索引，而不是温度本身，这样可以方便计算等待天数。
逆序遍历：从最后一天开始，逐步处理每一天的温度。这是因为我们需要查找每一天之后第一个更高的温度，而如果从前向后遍历就需要不断地返回去查找，效率较低。
栈的更新：每当我们遇到比栈顶元素小的温度时，栈顶元素的下一次更高温度就是当前温度，计算并记录等待的天数。如果栈顶元素比当前温度大，说明栈顶的温度就是下一个更高温度，记录下来。