每日温度（单调栈）

难度：⭐⭐⭐ 面试高频

考点

• 单调栈
• "下一个更大元素"类问题的通解
• 字节面试高频变体题

题目描述

给定一个整数数组 temperatures，表示每天的温度。返回一个数组 answer，其中 answer[i] 表示对于第 i 天，需要等待几天才能遇到比当天更高的温度。如果之后不存在更高温度，则 answer[i] = 0。

函数签名

func dailyTemperatures(temperatures []int) []int

示例

输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]

输入：temperatures = [30,40,50,60]
输出：[1,1,1,0]

输入：temperatures = [30,60,90]
输出：[1,1,0]

要求

1. 时间复杂度 O(n)，空间复杂度 O(n)
2. 使用单调栈解法

提示

• 维护一个单调递减栈（栈里存索引）
• 当前温度 > 栈顶温度时，弹出栈顶并计算天数差
• 每个元素最多入栈一次、出栈一次，总复杂度 O(n)

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures)
	result := make([]int, n)
	stack := make([]int, 0) // 存索引，保持栈内温度单调递减

	for i := 0; i < n; i++ {
		for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			result[top] = i - top
		}
		stack = append(stack, i)
	}
	return result
}