当前位置：首页 > news >正文

单调栈入门到精通：每日温度柱状图中最大的矩形

news 2026/4/28 0:14:00

一、入门题：739. 每日温度（中等）

题目描述

核心思路：单调栈的本质

代码实现（Java）

复杂度分析

二、进阶题：84. 柱状图中最大的矩形（困难）

题目描述

核心思路：用单调栈找边界

解题步骤

代码实现（Java）

复杂度分析

三、两道题的核心模板总结

通用解题步骤

今天我们用两道经典的「单调栈」题目，带你从入门到精通这个算法模板。

入门题：LeetCode 739. 每日温度
进阶题：LeetCode 84. 柱状图中最大的矩形

这两道题是单调栈的 “黄金模板”，搞懂它们，面试中 90% 的单调栈题目都能迎刃而解。

一、入门题：739. 每日温度（中等）

题目描述

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

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

核心思路：单调栈的本质

这道题的本质，是找「下一个比当前大的数」。

暴力解法是双重循环，时间复杂度 O (n²)，但我们可以用单调栈把它优化到 O (n)。

单调栈的核心逻辑：

我们维护一个栈，栈中元素是温度的索引，并且它们对应的温度是单调递减的。
遍历每一天的温度：
- 如果当前温度 > 栈顶索引对应的温度：说明找到了栈顶元素的 “下一个更高温度”。
- 弹出栈顶元素，计算两者的索引差，就是答案。
- 重复这个过程，直到栈顶元素对应的温度 >= 当前温度，再把当前索引入栈。

代码实现（Java）

java

运行

public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] answer = new int[n]; // 栈中存储索引，保证索引对应的温度单调递减 Deque<Integer> stack = new LinkedList<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int prevIndex = stack.pop(); answer[prevIndex] = i - prevIndex; } stack.push(i); } return answer; }

复杂度分析

时间复杂度：O (n)，每个元素最多入栈和出栈一次。
空间复杂度：O (n)，最坏情况下所有元素都入栈。

二、进阶题：84. 柱状图中最大的矩形（困难）

题目描述

给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

核心思路：用单调栈找边界

这道题的关键是，以每一根柱子的高度为矩形的高，找到它能扩展的最大宽度。

对于高度为h[i]的柱子，我们需要找到：
1. 左边第一个比它矮的柱子的索引left。
2. 右边第一个比它矮的柱子的索引right。
那么以h[i]为高的矩形的宽度就是right - left - 1，面积就是h[i] * (right - left - 1)。

而单调栈，正是解决 “找左右边界” 的神器。

解题步骤

哨兵优化：在数组首尾各加一个高度为 0 的哨兵，避免栈为空或无法出栈的边界情况。
维护单调递增栈：栈中存储柱子的索引，保证它们对应的高度是单调递增的。
遍历计算面积：
- 当遇到一个比栈顶元素矮的柱子时，栈顶元素找到了它的 “右边界”。
- 弹出栈顶元素cur，此时的栈顶就是它的 “左边界”。
- 计算以cur为高的矩形面积，并更新最大值。

代码实现（Java）

java

运行

public int largestRectangleArea(int[] heights) { // 哨兵优化，首尾加 0 int n = heights.length; int[] newHeights = new int[n + 2]; System.arraycopy(heights, 0, newHeights, 1, n); Deque<Integer> stack = new LinkedList<>(); int maxArea = 0; for (int i = 0; i < newHeights.length; i++) { // 维护单调递增栈 while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) { int curIndex = stack.pop(); int height = newHeights[curIndex]; int width = i - stack.peek() - 1; maxArea = Math.max(maxArea, height * width); } stack.push(i); } return maxArea; }