LeetCode 739. 每日温度

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 739. 每日温度

思路分析

单调递减栈

参考代码

func dailyTemperatures(T []int) []int {
	n := len(T)
	answer := make([]int, n)
	var stack []int // 单调栈

	for i := 0; i < n; i++ {
		// 当当前温度大于栈顶温度时，更新答案
		for len(stack) > 0 && T[i] > T[stack[len(stack)-1]] {
			index := stack[len(stack)-1] // 获取栈顶索引
			stack = stack[:len(stack)-1] // 弹出栈顶元素
			answer[index] = i - index    // 计算天数差
		}
		stack = append(stack, i) // 将当前索引压入栈中
	}

	return answer
}

时间复杂度：O (n)，其中 n 是气温列表的长度。

空间复杂度：O (n)，用于存储栈和结果数组。

func dailyTemperatures(temperatures []int) []int {
	n := len(temperatures)
	res := make([]int, n)
	var stack []int

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

时间复杂度：O(n)，每个元素最多入栈、出栈一次。

空间复杂度：O(n)，用于存储栈和 res 结果数组。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/19856294