739. 每日温度 Medium

给定一个整数数组 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]

解题思路

输入：一个整数数组 temperatures，表示每天的温度

输出：返回表示每天温度距离下一个更高温度的天数

本题属于 单调栈 问题。

• 我们可以维护一个递减的单调栈，从栈底到栈顶温度都是递减的
• 栈里存的都是索引 index

我们可以从后往前遍历数组，每次都拿当前温度和栈顶元素比较，只要比栈中元素大就移除栈内元素，直到遇到比当前温度大的索引为止

例如：80 -> [90, 78, 72, 70] =====> [90, 80]

当找到比当前温度大的索引之后，就得出当前温度的对应答案 ans[i] = st[-1] - i

最后我们遍历完整个数组后就得到了每一天的答案

代码实现

python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stack = []  # 单调递减栈，存储索引（栈顶是最近的温度较高的天）
        res = [0] * n  # 结果数组，默认值为0

        # 从后往前遍历（因为要找后面几天比今天热）
        for i in range(n - 1, -1, -1):
            current_temp = temperatures[i]

            # 栈中只保留比当前温度高的天数索引
            while stack and temperatures[stack[-1]] <= current_temp:
                stack.pop()

            # 如果栈不为空，说明找到了比当前温度高的那一天
            if stack:
                res[i] = stack[-1] - i  # 计算间隔天数

            # 当前天入栈，作为后面元素的“未来”
            stack.append(i)

        return res

javascript

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

    for (let i = temperatures.length - 1; i >= 0; i--) {
        const t = temperatures[i];
        while (st.length && t >= temperatures[st.at(-1)]) {
            st.pop();
        }

        if (st.length) {
            ans[i] = st.at(-1) - i;
        }

        st.push(i);
    }

    return ans;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

739 国际版

739 中文版