739. 每日温度

力扣题目链接 (opens new window)

题目描述

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

提示：

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

思路

最直观的做法是：对每一天都向右寻找第一个更高温度。最坏情况下，每个位置都要扫描后面的所有元素，时间复杂度是 O(n²)。

但本题要找的并不是右侧所有更高的温度，而是右侧第一个更高的温度。

什么时候应该想到单调栈呢？

通常遇到“找一个元素左边或右边第一个比它大（或小）的元素”时，就应该想到单调栈。

栈里存什么

栈里存温度还是下标？

题目最终要求的是等待天数，也就是两个位置的距离，所以栈中应该存放还没有找到答案的日期下标。通过下标既能取得温度 temperatures[i]，又能在找到答案时计算 i - index。

栈保持什么顺序

从左向右遍历温度。栈内下标对应的温度，从栈底到栈顶保持单调不增。

为什么要这样维护？

如果当前温度 temperatures[i] 高于栈顶日期的温度，那么当前日期就是栈顶日期右侧遇到的第一个更高温度。此时可以弹出栈顶，并记录：

answer[栈顶下标] = i - 栈顶下标

弹出一个元素后，当前温度还可能高于新的栈顶，因此这里要使用 while 连续处理，而不是只判断一次。

遍历时只有两种操作：

1. 当前温度不高于栈顶温度，直接将当前下标入栈
2. 当前温度高于栈顶温度，不断弹栈并计算等待天数，再将当前下标入栈

注意，相同温度不能触发弹栈，因为题目要求的是“更高”，不是“大于等于”。

每个下标最多入栈一次、出栈一次，所以虽然代码里有 while，整体时间复杂度仍然是 O(n)。

模拟过程

为了把“小于、等于、大于栈顶温度”三种情况都展示出来，沿用代码随想录原文中的示例：

temperatures = [73,74,75,71,71,72,76,73]
answer       = [1,1,4,2,1,1,0,0]

首先将下标 0 入栈，等待后面出现更高温度。

遍历到 74，它高于栈顶的 73。弹出下标 0，得到 answer[0] = 1 - 0 = 1，再将下标 1 入栈。

遍历到 75，同理弹出下标 1，记录 answer[1] = 1，再将下标 2 入栈。

遍历到第一个 71，它低于栈顶的 75，不能解决栈顶日期的问题，直接入栈。

遍历到第二个 71，它和栈顶温度相等。因为相等不算更高，所以仍然直接入栈。

遍历到 72，它高于栈顶的 71。先弹出下标 4，记录 answer[4] = 5 - 4 = 1。

此时新的栈顶仍然是 71，继续弹出下标 3，记录 answer[3] = 5 - 3 = 2。

新的栈顶是 75，当前温度 72 不再更高，停止弹栈，将下标 5 入栈。

遍历到 76，它先解决下标 5 对应的 72，记录 answer[5] = 1。

弹出后，76 仍高于新的栈顶 75，继续弹出下标 2，记录 answer[2] = 6 - 2 = 4。

将下标 6 入栈，此时栈中只剩下温度 76。

最后遍历到 73，它低于栈顶的 76，直接入栈。遍历结束后，下标 6 和 7 仍在栈中，说明它们右侧没有更高温度，对应答案保持初始化的 0。

解题代码

C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> answer(temperatures.size(), 0);
        stack<int> st;

        for (int i = 0; i < temperatures.size(); i++) {
            // 当前温度为栈顶日期找到了右侧第一个更高温度
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int index = st.top();
                st.pop();
                answer[index] = i - index;
            }
            st.push(i);
        }

        return answer;
    }
};

复杂度分析

• 时间复杂度：O(n)。每个下标最多入栈一次、出栈一次。
• 空间复杂度：O(n)。最坏情况下温度单调不升，所有下标都会留在栈中。

其他语言

Python3

from typing import List


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []

        for i, temperature in enumerate(temperatures):
            # 当前温度为栈顶日期找到了右侧第一个更高温度
            while stack and temperature > temperatures[stack[-1]]:
                index = stack.pop()
                answer[index] = i - index
            stack.append(i)

        return answer

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < temperatures.length; i++) {
            // 当前温度为栈顶日期找到了右侧第一个更高温度
            while (!stack.isEmpty()
                    && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i);
        }

        return answer;
    }
}

Go

func dailyTemperatures(temperatures []int) []int {
    answer := make([]int, len(temperatures))
    stack := make([]int, 0)

    for i, temperature := range temperatures {
        // 当前温度为栈顶日期找到了右侧第一个更高温度
        for len(stack) > 0 && temperature > temperatures[stack[len(stack)-1]] {
            index := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            answer[index] = i - index
        }
        stack = append(stack, i)
    }

    return answer
}

JS

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const answer = new Array(temperatures.length).fill(0);
    const stack = [];

    for (let i = 0; i < temperatures.length; i++) {
        // 当前温度为栈顶日期找到了右侧第一个更高温度
        while (
            stack.length > 0 &&
            temperatures[i] > temperatures[stack[stack.length - 1]]
        ) {
            const index = stack.pop();
            answer[index] = i - index;
        }
        stack.push(i);
    }

    return answer;
};

与代码随想录联系

我在代码随想录的739. 每日温度中，详细拆解了单调栈里存什么、保持什么顺序，以及当前元素和栈顶元素之间的三种大小关系。

这道题是单调栈专题的入门题。理解“当前元素帮助栈顶元素确定答案”之后，可以继续学习：

• 496. 下一个更大元素 I：把下一个更大元素映射回另一个数组
• 503. 下一个更大元素 II：在循环数组中寻找下一个更大元素
• 42. 接雨水：弹栈时同时使用左边界、底部和右边界计算雨水
• 84. 柱状图中最大的矩形：寻找左右两侧第一个更小的元素

把这几道题放在一起练习，就能逐步看清单调栈到底在记录什么，以及一次弹栈为什么能够确定答案。