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

目录一、入门题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)。单调栈的核心逻辑我们维护一个栈栈中元素是温度的索引并且它们对应的温度是单调递减的。遍历每一天的温度如果当前温度 栈顶索引对应的温度说明找到了栈顶元素的 “下一个更高温度”。弹出栈顶元素计算两者的索引差就是答案。重复这个过程直到栈顶元素对应的温度 当前温度再把当前索引入栈。代码实现Javajava运行public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] answer new int[n]; // 栈中存储索引保证索引对应的温度单调递减 DequeInteger 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]的柱子我们需要找到左边第一个比它矮的柱子的索引left。右边第一个比它矮的柱子的索引right。那么以h[i]为高的矩形的宽度就是right - left - 1面积就是h[i] * (right - left - 1)。而单调栈正是解决 “找左右边界” 的神器。解题步骤哨兵优化在数组首尾各加一个高度为 0 的哨兵避免栈为空或无法出栈的边界情况。维护单调递增栈栈中存储柱子的索引保证它们对应的高度是单调递增的。遍历计算面积当遇到一个比栈顶元素矮的柱子时栈顶元素找到了它的 “右边界”。弹出栈顶元素cur此时的栈顶就是它的 “左边界”。计算以cur为高的矩形面积并更新最大值。代码实现Javajava运行public int largestRectangleArea(int[] heights) { // 哨兵优化首尾加 0 int n heights.length; int[] newHeights new int[n 2]; System.arraycopy(heights, 0, newHeights, 1, n); DequeInteger 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; }复杂度分析时间复杂度O (n)每个元素最多入栈和出栈一次。空间复杂度O (n)最坏情况下所有元素都入栈。三、两道题的核心模板总结这两道题其实是单调栈的两种典型应用场景表格题目栈的单调性核心作用每日温度单调递减栈找下一个更大元素柱状图最大矩形单调递增栈找左右第一个更小元素通用解题步骤明确问题你要找的是 “下一个更大 / 更小”还是 “左右边界”选择单调性找下一个更大元素用单调递减栈。找下一个更小元素用单调递增栈。处理边界使用哨兵在数组首尾加 0是简化代码的常用技巧。。