单调栈适合解柱状图最大矩形，因其能高效找到每个柱子左右最近更小元素以确定延展宽度；通过维护递增索引栈，遇更矮柱即弹栈计算面积，宽度为i−stack[−1]−1（栈空时左界为−1），需末尾补0并初始化栈为[−1]确保全覆盖。
为什么单调栈适合解柱状图最大矩形
因为每个柱子能向左右“延展”的最大宽度，取决于它两侧第一个比它矮的柱子位置——这正是单调栈擅长捕捉的“最近更小元素”关系。用栈维护递增高度索引，一旦遇到更矮柱子，就弹出栈顶并计算以该柱子为高的矩形面积。
核心逻辑：弹栈时如何算宽度和面积
弹出 idx 时，heights[idx] 是当前矩形的高；左边界是新栈顶（即上一个未被弹出的索引），右边界是当前遍历位置 i。宽度 = i - stack[-1] - 1（若栈为空，则左边界为 -1，宽度 = i）。
- 栈中存的是下标，不是高度值
- 必须在原数组末尾补一个 0，确保所有柱子都会被弹出计算一次
- 初始化栈为
[-1]，可统一处理左边界为空的情况
Python 实现要点与易错点
常见错误是边界计算错位，比如把宽度写成 i - stack[-1] 或漏掉补 0 步骤，导致漏算最右一列或栈底元素。
def largestRectangleArea(heights):
heights.append(0) # 强制清空栈
stack = [-1]
max_area = 0
for i in range(len(heights)):
while 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
-
heights.append(0)必须在循环前做，且不能用heights + [0]（会新建列表，原引用失效） -
stack[-1]在stack为空时报错，所以初始设为[-1]，保证stack[-1]始终合法 - 比较条件是
heights[i] ，不是 ≤，否则相同高度会过早弹出，破坏左边界准确性
时间复杂度和实际调试建议
每个下标最多入栈、出栈各一次，均摊 O(n)，但常数较大。调试时建议打印每次弹栈的 i、idx、w、h，尤其关注 stack = [-1] 后第一次弹出时的宽度是否为 i（例如 heights = [2,1] 中，处理到 i=1 时弹出 0，宽度应为 1，不是 0）。
立即学习“Python免费学习笔记（深入）”；
最容易被忽略的是：当多个柱子高度相同时，单调栈仍保持“严格递增”逻辑，靠“小于”而非“小于等于”来触发计算——这点决定了相同高度的柱子不会互相干扰左边界，各自等待真正更小的右边界出现。
