【每日算法】LeetCode 84. 柱状图中最大的矩形-平芜编程栈

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 84. 柱状图中最大的矩形：从暴力到单调栈的优雅解法

1. 题目描述

LeetCode 84题“柱状图中最大的矩形”要求：给定一个整数数组heights，表示柱状图中各个柱子的高度，每个柱子的宽度为1，且彼此相邻。需要找出该柱状图中能够勾勒出的最大矩形的面积。

示例：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大矩形面积为10，对应高度为5的柱子，宽度为2（即从索引2到3的柱子，但实际计算以高度5向左右延伸）。

约束条件：

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

2. 问题分析

该问题的核心在于：对于每个柱子，以其高度作为矩形高度时，矩形的最大宽度由其左右两侧第一个比它矮的柱子决定。因此，最大矩形面积可通过遍历每个柱子，计算以该柱子高度为高的最大矩形面积，并取全局最大值得到。

关键转换：

对于柱子i，高度为h[i]，向左找到第一个高度小于h[i]的索引left，向右找到第一个高度小于h[i]的索引right。
此时，矩形宽度为right - left - 1，面积为h[i] * (right - left - 1)。
遍历所有i，计算最大面积。

这本质上是寻找每个柱子的“左右边界”，类似前端中计算元素在布局中的扩展范围。

3. 解题思路

3.1 暴力解法（朴素扩展）

对于每个柱子，向左右两侧扩展，直到遇到高度更小的柱子，计算面积。该方法直观但效率低。

时间复杂度：O(n²)，其中n为柱子数量。
空间复杂度：O(1)。
优点：简单易懂，适合小数据量。
缺点：在大数据量（如n=10⁵）时超时，不适合生产环境。

3.2 单调栈解法（最优）

利用单调递增栈（Monotonic Stack）在一次遍历中高效找到每个柱子的左右边界。栈中存储柱子索引，保持高度单调递增，当遇到更矮柱子时弹出栈顶并计算面积。

时间复杂度：O(n)，每个柱子入栈和出栈一次。
空间复杂度：O(n)，用于栈存储。
优点：高效，适用于大规模数据，是面试和工程中的标准解法。
缺点：代码逻辑稍复杂，需要理解栈的操作。

为什么单调栈有效：
维护递增栈确保栈中每个柱子的左边界是栈中前一个索引（或哨兵），右边界是当前遍历到的索引。通过添加哨兵（如高度0）处理边界情况，简化代码。

4. 代码实现

以下使用JavaScript实现，作为前端开发者熟悉的语言。

4.1 暴力解法代码

functionlargestRectangleArea(heights){letmaxArea=0;constn=heights.length;for(leti=0;i<n;i++){letleft=i;// 向左扩展找到第一个比当前矮的柱子while(left>=0&&heights[left]>=heights[i]){left--;}letright=i;// 向右扩展找到第一个比当前矮的柱子while(right<n&&heights[right]>=heights[i]){right++;}constwidth=right-left-1;maxArea=Math.max(maxArea,heights[i]*width);}returnmaxArea;}

4.2 单调栈解法代码（最优）

functionlargestRectangleArea(heights){letmaxArea=0;conststack=[];// 单调递增栈，存储索引// 添加哨兵：开头和末尾添加高度0，简化边界处理heights=[0,...heights,0];for(leti=0;i<heights.length;i++){// 当当前高度小于栈顶高度时，弹出栈顶并计算面积while(stack.length&&heights[stack[stack.length-1]]>heights[i]){consth=heights[stack.pop()];// 弹出高度constleft=stack[stack.length-1];// 左边界是栈中下一个索引constwidth=i-left-1;maxArea=Math.max(maxArea,h*width);}stack.push(i);// 将当前索引入栈}returnmaxArea;}

代码解释：

哨兵0确保栈能清空并计算所有可能矩形。
栈维护递增高度索引，弹出时计算以弹出高度为高的矩形面积。
此方法只需一次遍历，效率极高。

5. 各实现思路的复杂度、优缺点对比表格

方法	时间复杂度	空间复杂度	优点	缺点
暴力解法	O(n²)	O(1)	实现简单，易于理解；适合小规模数据或快速原型。	效率低，在数据量大时（如n=10⁵）会超时；不适用于生产环境。
单调栈解法	O(n)	O(n)	高效，一次遍历解决；适合大规模数据处理；是面试和工程中的标准解。	代码逻辑稍复杂；需要额外空间存储栈；但实际中空间可接受。