本文概览本文讲解柱状图中最大的矩形的核心思路用单调递增栈一次遍历找到每根柱子的左右边界从 O(n²) 降到 O(n)一、题目二、题目分析1. 题目要求给定一个非负整数数组heights每个元素表示柱状图中该位置柱子的高度求能勾勒出的最大矩形面积。例子heights [2, 1, 5, 6, 2, 3]柱状图示意每列代表一根柱子列高 高度值 6 5 6 5 6 5 6 5 6 3 2 5 6 2 3 2 1 5 6 2 3 --------------------- 0 1 2 3 4 5 ← 索引最大矩形是中间的[5, 6]高度 5、宽度 2面积 5 × 2 10。2. 怎么才算一个矩形随便挑一根柱子比如挑索引 4高度 2的柱子来看0 1 2 3 4 5 ← 索引 2 1 5 6 2 3 ← 高度 ↑ 当前柱子索引4以这根柱子的高度 2 作为矩形的高那么这个矩形要往左右扩展什么情况下这个高度不成立左边或右边出现了一根比它矮的柱子这个高度就不成立了。因为矩形必须连续碰到更矮的柱子就撑不过去。找左右边界0 1 2 3 4 5 ← 索引 2 1 5 6 2 3 ← 高度 ↑ ↑ 左边界 当前柱子 (索引1) (索引4) → 左边界高度 1 2矩形往左扩到这就停 → 右边界右边没有比 2 更矮的扩到最右边为止左边界索引 1高度 1是第一根比 2 矮的柱子右边界没有比它更矮的所以到最右边为止3. 面积公式怎么算矩形能覆盖的柱子是[5, 6, 2, 3]宽度肉眼可见是 4。但代码里怎么算技巧右边界没有时自己在数组末尾补一根高度为 0 的虚拟柱子。0 1 2 3 4 5 ← 索引 2 1 5 6 2 3 ← 原数组 2 1 5 6 2 3 0 ← 末尾补一个 0 ↑ 虚拟柱子索引6现在右边界就是索引 6左边界是索引 1宽度公式width right - left - 1 6 - 1 - 1 4 area height * width 2 * 4 8公式记忆左右边界都是比当前柱子矮的柱子所以宽度要把两根边界柱子都排除掉即right - left - 1。4. 暴力思路的问题最直觉的做法遍历每根柱子每次都向左找第一根比它矮的向右找第一根比它矮的。for(inti0;in;i){// 找左边界intleft-1;for(intji-1;j0;j--){if(heights[j]heights[i]){leftj;break;}}// 找右边界intrightn;for(intji1;jn;j){if(heights[j]heights[i]){rightj;break;}}// 计算面积maxAreaMath.max(maxArea,heights[i]*(right-left-1));}时间复杂度O(n²)每根柱子都要重复扫已经扫过的元素。5. 核心观察暴力遍历中的浪费关键问题暴力遍历里找柱子 i 的左边界时已经把[0, i-1]都扫了一遍但找柱子i1的左边界时又要重新扫[0, i]这些信息完全重复了。优化思路能不能只遍历一次就按顺序找到每根柱子的左右边界关键数据结构单调递增栈。维护一个高度递增的栈栈里存索引当一根新柱子比栈顶柱子矮时栈顶柱子的右边界就找到了就是这根新柱子栈顶柱子的左边界就是它在栈里的下一个元素栈顶出栈后新的栈顶就是左边界和暴力最大的区别不是实时算每根柱子的面积而是延时计算——一直憋着算栈顶到最后一样能算完所有柱子。三、思路概览publicintlargestRectangleArea(int[]heights){if(heights.length0){return0;}intmaxArea0;intnheights.length;// 头尾各加一个 0 作为哨兵int[]newHeightnewint[n2];System.arraycopy(heights,0,newHeight,1,n);// 单调递增栈存索引DequeIntegerstacknewArrayDeque();for(inti0;in2;i){// 若栈不为空且当前元素小于栈顶元素则弹出栈顶元素并计算面积while(!stack.isEmpty()newHeight[i]newHeight[stack.peekLast()]){// 当前值高度intheightnewHeight[stack.pollLast()];// 左边界intleftstack.peekLast();// 右边界intrighti;// 宽度intwidthright-left-1;// 面积maxAreaMath.max(maxArea,height*width);}// 入栈stack.addLast(i);}returnmaxArea;}思路简要说明哨兵数组在原数组头尾各加一个 0保证栈内元素最后全部能弹出单调递增栈栈内索引对应的高度从底到顶递增左边界栈顶出栈后新的栈顶就是它的左边界右边界触发栈顶出栈的当前柱子就是右边界面积公式height * (right - left - 1)延时计算不是实时算每根柱子而是憋住算栈顶最后一定能算完全部四、思路详解第一步左右边界到底怎么确定回到核心定义以柱子 i 的高度为矩形的高时矩形能向左右延伸到哪0 1 2 3 4 5 ← 索引 2 1 5 6 2 3 ← 高度 ↑ ↑ 左边界 当前柱子 i 第一根更矮左边界从柱子 i 往左看第一根比heights[i]矮的柱子右边界从柱子 i 往右看第一根比heights[i]矮的柱子矩形的高是heights[i]宽度是中间这段不含边界所以width right - left - 1 area heights[i] * (right - left - 1)第二步为什么是单调递增栈问题怎么一次遍历就把每根柱子的左右边界都找出来思考如果遍历过程中已经处理过的柱子的高度是递增的那么对于一根新柱子如果新柱子比栈顶高 → 直接入栈栈顶的右边界还没到如果新柱子比栈顶矮 →栈顶柱子的右边界就是这根新柱子那左边界呢栈顶柱子出栈后新的栈顶就是它在栈里的下一个元素这个元素的高度比它矮因为递增所以就是它的左边界。栈内高度递增左边是栈底右边是栈顶 [A] [B] [C] ↑ C 是当前要算的柱子 新柱子 D 比 C 矮 C 出栈 C 的左边界 B新的栈顶 C 的右边界 D area heights[C] * (D - B - 1)单调递增栈的本质栈内每根柱子的左边界就是它在栈里的前一根柱子右边界由后面第一个比它矮的柱子触发。第三步为什么要延时计算暴力思路遍历到柱子 i 时立刻算它的面积 → 需要重新扫左右边界 → O(n²)单调栈思路遍历到柱子 i 时不一定是算柱子 i 的面积而是算栈顶柱子的面积。为什么这样也能算完所有柱子每根柱子入栈一次每根柱子出栈一次被某个更矮的柱子触发出栈的那一刻它的左右边界都已确定立即算面积所以遍历结束时所有柱子都必然被算过一次。第四步为什么要加哨兵问题如果数组本身就是递增的比如[1, 2, 3, 4, 5]遍历到最后一根时栈里所有元素都没机会出栈因为没有更矮的柱子触发它们。解决在数组末尾加一个 00 比任何柱子都矮必然能把栈里所有元素全部弹出。开头也要加 0保证第一根柱子也有左边界栈底的 0 就是它的左边界同时避免栈空判断。0 2 1 5 6 2 3 0 ← newHeight头尾各补一个 0 ↑ ↑ 头哨兵 尾哨兵 索引0 索引7哨兵的双重作用尾哨兵保证遍历结束时栈内所有元素都能弹出确保每根柱子都被算到头哨兵作为第一根柱子的左边界避免stack.peekLast()在栈只有一个元素时出错第五步为什么是 O(n)看起来有 while 嵌套在 for 里应该是 O(n²)实际上每个索引最多入栈一次出栈一次。外层 for 循环n 2 次内层 while 循环所有索引总共出栈 n 2 次所以总操作次数是 2(n2)时间复杂度O(n)。完整执行过程以heights [2, 1, 5, 6, 2, 3]为例加哨兵后newHeight [0, 2, 1, 5, 6, 2, 3, 0]长度 8初始stack [], maxArea 0 i0, height0 栈空0 入栈 stack [0] i1, height2 2 0栈顶2 入栈 stack [0, 1] i2, height1 1 2栈顶弹出 1 height2, left0, right2, width2-0-11, area2×12 maxArea max(0, 2) 2 1 0栈顶1 入栈 stack [0, 2] i3, height5 5 1栈顶5 入栈 stack [0, 2, 3] i4, height6 6 5栈顶6 入栈 stack [0, 2, 3, 4] i5, height2 2 6栈顶弹出 4 height6, left3, right5, width5-3-11, area6×16 maxArea max(2, 6) 6 2 5栈顶弹出 3 height5, left2, right5, width5-2-12, area5×210 maxArea max(6, 10) 10 2 1栈顶2 入栈 stack [0, 2, 5] i6, height3 3 2栈顶3 入栈 stack [0, 2, 5, 6] i7, height0尾哨兵 0 3栈顶弹出 6 height3, left5, right7, width7-5-11, area3×13 maxArea max(10, 3) 10 0 2栈顶弹出 5 height2, left2, right7, width7-2-14, area2×48 maxArea max(10, 8) 10 0 1栈顶弹出 2 height1, left0, right7, width7-0-16, area1×66 maxArea max(10, 6) 10 0 0栈顶不满足 条件停止弹出 0 入栈 stack [0, 7] 遍历结束maxArea 10 ✓关键观察最大面积 10 在i5时算出对应中间的柱子[5, 6]高度 5宽度 2尾哨兵 0 在i7时把栈内剩余柱子全部弹出保证不漏算最后栈里剩[0, 7]两个哨兵不影响结果与接雨水的对比维度接雨水柱状图中最大的矩形关注点凹槽能存多少水单根柱子能撑多大矩形单调栈方向递减栈找下一个更高递增栈找下一个更矮触发条件新柱子比栈顶高新柱子比栈顶矮边界定义左右更高柱子围成凹槽左右更矮柱子围成矩形五、总结柱状图中最大的矩形的核心思路矩形定义以柱子 i 的高度为高左右边界是第一根比它矮的柱子面积公式height * (right - left - 1)单调递增栈栈顶出栈后新栈顶是左边界触发出栈的柱子是右边界延时计算遍历到新柱子时算的是栈顶柱子的面积不是新柱子的哨兵技巧头尾加 0保证所有柱子都能出栈被算到时间复杂度 O(n)每个索引最多入栈一次出栈一次空间复杂度 O(n)栈最多存储 n2 个索引单调栈的适用场景找下一个更大/更小的元素需要维护一个单调序列暴力遍历中有重复的边界查找