LeetCode LCR 038. 每日温度

Categories:

题目描述
思路分析
1. 解法一：单调栈（推荐）
相似题目

题目描述

✅ LCR 038. 每日温度

思路分析

解法一：单调栈（推荐）

核心思路：

问题本质：对数组中每个元素，找其右侧第一个比它大的元素的距离，这是单调栈最经典的应用场景。

单调栈语义：维护一个单调递减栈，栈中存储下标。栈中每个下标对应的温度值单调递减，意味着这些位置的”右侧第一个更高温度”还未找到。

触发时机：遍历到下标 i 时，若 temperatures[i] > temperatures[stack.top]，则栈顶元素找到了答案，弹出并计算距离 i - j，持续弹出直到栈空或栈顶温度 >= temperatures[i]。

为何存下标：需要计算天数差（位置之差），存下标可同时通过 temperatures[idx] 查温度，信息完整。

遍历结束后，栈中剩余的下标对应位置在右侧无更高温度，答案默认为 0。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，每个元素最多入栈出栈各一次

空间复杂度：O(n)，单调栈最多存储 n 个下标

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // 单调递减栈，存储下标
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 当前温度大于栈顶温度时，栈顶元素找到了右侧第一个更高温度
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int pre = stack.pop();
                // 天数差即为答案
                res[pre] = i - pre;
            }
            stack.push(i);
        }
        return res;
    }
}

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
}

相似题目

题目	难度	考察点
496. 下一个更大元素 I	简单	单调栈、哈希表
503. 下一个更大元素 II	中等	单调栈
901. 股票价格跨度	中等	单调栈
84. 柱状图中最大的矩形	困难	单调栈
42. 接雨水	困难	单调栈、双指针
85. 最大矩形	困难	单调栈
1019. 链表中的下一个更大节点	中等	单调栈
907. 子数组的最小值之和	中等	单调栈
1475. 商品折扣后的最终价格	简单	单调栈
2104. 子数组范围和	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/78184662