【单调栈】每日温度

每日温度

题目给定每日气温数组 temperatures，求每一天距离下一次出现更高气温需要等待的天数，记为 answer[i]。如果之后气温都不会升高，则对应位置填 0。

一个较为容易想到的直观解法是：

对于每个位置 i，从 i + 1 开始向右寻找，直到找到第一个比 temperatures[i] 更高的气温。

如果找到了，记录两个位置之间的距离；如果遍历到了数组末尾还没有找到，就记录 0。

基于这一思路可以写出代码：

▼
java
复制代码
public int[] dailyTemperatures(int[] temperatures) {
    int[] answer = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
        int nextIndex;
        for (nextIndex = i + 1; nextIndex < temperatures.length; nextIndex++) {
            if (temperatures[i] < temperatures[nextIndex]) {
                break;
            }
        }
        answer[i] = nextIndex < temperatures.length ? nextIndex - i : 0;
    }
    return answer;
}

这种解法在最坏情况下，例如气温一直递减，每个位置都可能需要向右遍历很长一段距离，因此时间复杂度为 $O(n^2 )$，其中 $n$ 为数组长度。

这一暴力解法的思路很直观，但是对于每个位置，我们都需要独立地向右查找，可能存在重复遍历。

那么，能否在遍历气温数组的过程中，利用已经遍历过的信息，减少重复计算，从而提高算法的效率呢？

我们先来看一个简单的例子：

▼
java
复制代码
temperatures = [73, 71, 69, 72]

对于气温 73，向右查找后发现没有更高的气温，因此答案为 0。

对于气温 71，需要经过 69，才能找到更高的气温 72，因此答案为 2。

对于气温 69，同样需要向右查找，才能找到气温 72，因此答案为 1。

我们注意到，气温 72 不仅是 69 的答案，也是 71 的答案。

那么，当我们遍历到 72 时，能否利用它，同时处理前面多个位置的「下一个更大元素」问题，而不必针对每个位置独立地向右查找？

为此，我们可以换一种思路：不再针对每个气温向右寻找答案，而是从左向右遍历，让当前气温主动去解决前面尚未找到答案的元素。

具体来说，我们可以维护一个集合，记录那些尚未找到更高气温的元素。

当遍历到一个新气温时，检查集合中的元素，如果某个元素的气温低于当前气温，那么当前气温就找到了它的答案，我们便可以将它移出集合。

那么，应该如何组织这些尚未找到答案的元素，才能快速判断哪些元素可以由当前气温解决呢？

观察前面的例子，候选气温依次为 73、71、69，它们是降序排列的。因此，我们可以优先检查最后加入的元素。

当遇到 72 时，它比 69 大，因此可以确定 69 的答案，并将其移出集合。接着检查 71，发现 72 同样比它大，于是也可以将其移出集合。

由此，我们可以让候选元素始终按照气温从高到低排列。每当遇到新的气温，就从最后一个候选元素开始，不断移除气温低于当前气温的元素。

对于每一个被移除的元素，当前气温就是它所等待的下一次更高气温，因此可以直接确定它的答案。 重复这一过程，直到遇到一个气温不低于当前气温的元素，或者集合为空。

最后，将当前气温加入集合，作为一个尚未找到答案的新候选元素。

观察上述操作，我们只需要在集合的一端添加和移除元素。因此，可以使用栈来存储这些尚未找到答案的候选元素。

由于栈内的元素从栈底到栈顶按照气温从高到低排列，因此这个栈具有单调性，这样的栈称为单调栈（monotonic stack）。

在本题中，我们维护的是一个单调递减栈：栈中的元素从栈底到栈顶按照气温从高到低排列，栈顶元素就是最后加入的候选元素。

基于这一思路，我们可以写出如下代码：

▼
java
复制代码
public int[] dailyTemperatures(int[] temperatures) {
    // 对于本题，我们在单调栈中存储的是尚未找到更高气温的元素下标
    Deque<Integer> stack = new ArrayDeque<>();
    int[] answer = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
        // 当前气温更高，说明栈顶元素找到了下一个更高气温
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }
    return answer;
}

复杂度分析：

时间复杂度为 $O(n)$：虽然代码中有嵌套的 while 循环，但每个元素最多入栈、出栈一次。因此，总体时间复杂度为 $O(n)$。
空间复杂度为 $O(n)$：不计入答案数组所需的空间，单调栈最多存储 $n$ 个元素。

实际上，本题是一个经典问题——下一个更大元素（Next Greater Element）问题的变体。

原问题描述的是：对于数组中的每个元素，我们需要找到其右侧第一个比它更大的元素。而本题则是要求我们计算二者之间的距离。

类似地，如果将条件改为寻找右侧第一个更小的元素，就得到了下一个更小元素（Next Smaller Element）问题。如果改变查找方向，还可以研究左侧第一个更大或更小的元素。

这类问题统称为最近更大/更小元素问题。当题目要求寻找每个元素左侧或右侧第一个更大或更小的元素时，可以考虑使用单调栈，通过空间换时间，将时间复杂度优化到 $O(n)$。

每日温度

目录

目录