1. 问题背景与核心挑战
柱形图最大矩形问题（LeetCode 84题，原输入有误）是算法面试中的经典难题，要求在一系列相邻且宽度为1的柱形中，找出能勾勒出的最大矩形面积。这个问题看似简单，但O(n²)的暴力解法在面试中毫无竞争力，而最优解的单调栈思路又需要巧妙的思维转换。
我第一次遇到这个问题时，尝试用双指针法折腾了两小时无果，直到理解栈如何维护"最近较小值"的特性才豁然开朗。这个算法在现实中有广泛应用场景，比如计算卫星地图中的最大建筑占地面积、股票分析中的支撑阻力位识别等。
2. 暴力解法与性能瓶颈
2.1 双重循环实现
最直观的方法是对于每个柱子，向左右两侧扩展直到遇到更矮的柱子：
def largestRectangleArea(heights): max_area = 0 n = len(heights) for i in range(n): left = i while left >= 0 and heights[left] >= heights[i]: left -= 1 right = i while right < n and heights[right] >= heights[i]: right += 1 max_area = max(max_area, (right - left - 1) * heights[i]) return max_area时间复杂度O(n²)，在LeetCode上会超时。主要浪费在于重复计算——当柱子高度呈递增序列时，内层while循环每次都要从头扫描。
2.2 暴力法的优化空间
可以通过预处理来存储每个位置左右边界：
- 从左向右扫描记录lastLessFromLeft数组
- 从右向左扫描记录lastLessFromRight数组 这样虽然仍为O(n²)，但实际运行时间会缩短。不过面试官期待的是更优解。
3. 单调栈最优解法
3.1 算法核心思想
维护一个栈，存储的是可能作为矩形左边界的柱子索引。当遇到新柱子时：
- 比栈顶高：直接入栈（当前柱子可能作为右边界的左边界）
- 比栈顶低：弹出栈顶并计算面积，直到栈顶柱子比当前矮
关键点：栈内柱子高度始终保持单调递增，这样栈内每个柱子的"下一个更小"就是当前柱子
3.2 完整实现代码
def largestRectangleArea(heights): stack = [] heights = [0] + heights + [0] # 边界处理技巧 max_area = 0 for i in range(len(heights)): while stack and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area这个O(n)解法有几个精妙之处：
- 首尾补0避免空栈判断
- 宽度计算利用栈的单调性
- 每个柱子只入栈出栈一次
4. 算法正确性证明
4.1 单调栈的数学性质
设栈内元素为s[0...k]，满足： heights[s[0]] < heights[s[1]] < ... < heights[s[k]]
当遇到heights[i] < heights[s[k]]时：
- 对于弹出的s[k]，其右边界显然是i
- 左边界是s[k-1]（因为s[k]是s[k-1]之后第一个>=它的柱子）
4.2 边界条件处理
首尾补0的两个作用：
- 开头的0保证第一个真实柱子能顺利入栈
- 结尾的0保证所有柱子都能被弹出计算
如果不补0，代码中需要增加大量判空逻辑，比如：
while stack and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 if stack else i # 处理栈空情况 max_area = max(max_area, h * w)5. 实际应用与变种问题
5.1 真实场景应用案例
- 地图分析：找出卫星图像中最大的连续建筑区域
- 股票分析：识别K线图中的关键支撑/阻力位
- 广告投放：计算网页中最大可投放广告区域
5.2 常见变种题目
- 二维矩阵中的最大矩形（LeetCode 85题）
- 解法：将矩阵逐行转化为柱形图高度
- 带障碍物的最大矩形
- 需要修改高度计算规则
- 最大正方形（LeetCode 221题）
- 类似思路但需要额外维护宽度
6. 调试技巧与常见错误
6.1 典型错误案例
错误实现1：漏处理相等情况
while stack and heights[i] <= heights[stack[-1]]: # 应该用<会导致重复计算相同高度的柱子
错误实现2：宽度计算错误
w = i - stack[-1] # 应该-1少减1会导致宽度多算一个单位
6.2 调试建议
- 先用小测试用例验证：
- [2,1,2] → 最大面积3
- [3,1,3,2,2] → 最大面积6
- 打印栈状态和中间结果：
print(f"i={i}, stack={stack}, max_area={max_area}")- 可视化柱形图辅助理解
7. 性能优化进阶
7.1 空间优化方案
原始算法需要O(n)空间存储栈，可以进一步优化：
- 分治法：O(nlogn)时间复杂度
- 线段树：O(nlogn)但实现复杂
不过在实际面试中，单调栈解法已经足够优秀。
7.2 并行计算可能性
对于超大规模数据(如地图分析)，可以将柱形图分段：
- 切分数据块并计算局部最大值
- 合并时处理边界区域的矩形 但要注意负载均衡和通信开销。
8. 面试实战要点
8.1 白板编码技巧
- 先说明暴力解法及其缺陷
- 引出单调栈思路时画图演示：
- 画出柱形图和栈的变化过程
- 标注关键步骤的面积计算
- 主动讨论边界条件（空输入、全等高等）
8.2 常见follow-up问题
- 如何修改算法求最大正方形？
- 如果柱子宽度不固定怎么处理？
- 如何扩展到二维情况？
我在多次面试中总结的经验是：解释清楚"为什么栈要单调递增"这个核心点，就能让面试官认可你的理解深度。
