柱状图中最大的矩形

怎样从“heights=[2,1,5,6,2,3],城市天际线最大广告牌面积。”推导出 单调栈 · 矩形，并证明每次状态变化都不会漏掉答案？

中心结论：单调递增栈存等待右边界的下标;遇更矮柱弹栈,rightLess=i,leftLess=新栈顶,width=i-leftLess-1;末尾 append 0 哨兵清算。

给出每个直方图的高度，要求在这些直方图之中找到面积最大的矩形，输出矩形的面积。

在本站主例中，heights=[2,1,5,6,2,3],城市天际线最大广告牌面积。

算法最终需要得到或观察：最大矩形面积 10(高 5 宽 2, index 2-3)。

为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“单调候选队列”，明确答案需要观察什么。
2. 2状态只维护 stack(下标)、扫描 i、leftLess/rightLess、maxArea。
3. 3转移每一步按照 单调递增栈存等待右边界的下标;遇更矮柱弹栈,rightLess=i,leftLess=新栈顶,width=i-leftLess-1;末尾 append 0 哨兵清算。
4. 4收尾读取 最大矩形面积 10(高 5 宽 2, index 2-3)。，并复核边界与复杂度。

栈或队列中保存的是仍未找到结论、且保持单调关系的下标。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：stack(下标)、扫描 i、leftLess/rightLess、maxArea。

用单调栈依次保存直方图的高度下标，一旦出现高度比栈顶元素小的情况就取出栈顶元素，单独计算一下这个栈顶元素的矩形的高度。然后停在这里(外层循环中的 i--，再 ++，就相当于停在这里了)，继续取出当前最大栈顶的前一个元素，即连续弹出 2 个最大的，以稍小的一个作为矩形的边，宽就是 2 计算面积…………如果停在这里的下标代表的高度一直比栈里面的元素小，就一直弹出，取出最后一个比当前下标大的高度作为矩形的边。宽就是最后一个比当前下标大的高度和当前下标 i 的差值。计算出面积以后不断的更新 maxArea 即可。

单调递增栈存等待右边界的下标;遇更矮柱弹栈,rightLess=i,leftLess=新栈顶,width=i-leftLess-1;末尾 append 0 哨兵清算。

执行过程中持续维护：stack(下标)、扫描 i、leftLess/rightLess、maxArea。

正确性依赖以下不变量：栈里放的是还在等待右边第一个更矮柱子的下标,栈内高度单调递增。；弹栈时 rightLess=当前 i,leftLess=弹栈后栈顶,width=i-leftLess-1。

面试时可以压缩为：每柱作最低高,左右第一个更矮柱定宽;单调递增栈维护等待右边界的下标,遇更矮则弹栈结算;append 0 哨兵清空栈;时间 O(n) 空间 O(n)。

落到当前题，执行机制可以压缩为：单调递增栈存等待右边界的下标;遇更矮柱弹栈,rightLess=i,leftLess=新栈顶,width=i-leftLess-1;末尾 append 0 哨兵清算。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入heights=[2,1,5,6,2,3],城市天际线最大广告牌面积。 因为：单调递增栈存等待右边界的下标;遇更矮柱弹栈,rightLess=i,leftLess=新栈顶,width=i-leftLess-1;末尾 append 0 哨兵清算。
2. 2以高 2 扩宽 1,面积 2当前更小高度触发结算。 因为：宽度由左右边界决定。
3. 3以高 6 扩宽 1,面积 6当前更小高度触发结算。 因为：宽度由左右边界决定。
4. 4以高 5 扩宽 2,面积 10当前更小高度触发结算。 因为：宽度由左右边界决定。
5. 5以高 3 扩宽 1,面积 3当前更小高度触发结算。 因为：宽度由左右边界决定。
6. 6以高 1 扩宽 6,面积 6当前更小高度触发结算。 因为：宽度由左右边界决定。
7. 7最大矩形面积 10栈空。 因为：O(n) 单调栈。
8. 8收尾与复杂度最大矩形面积 10(高 5 宽 2, index 2-3)。 因为：时间 O(n) · 空间 O(n)。单调递增栈存等待右边界的下标;遇更矮柱弹栈,rightLess=i,leftLess=新栈顶,width=i-leftLess-1;末尾 append 0 哨兵清算。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func largestRectangleArea(heights []int) int {
	maxArea := 0
	n := len(heights) + 2
	// Add a sentry at the beginning and the end
	getHeight := func(i int) int {
		if i == 0 || n-1 == i {
			return 0
		}
		return heights[i-1]
	}
	st := make([]int, 0, n/2)
	for i := 0; i < n; i++ {
		for len(st) > 0 && getHeight(st[len(st)-1]) > getHeight(i) {
			// pop stack
			idx := st[len(st)-1]
			st = st[:len(st)-1]
			maxArea = max(maxArea, getHeight(idx)*(i-st[len(st)-1]-1))
		}
		// push stack
		st = append(st, i)
	}
	return maxArea
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="largest-rectangle", heights=[2,1,5,6,2,3]
    //    期望：最大矩形面积 10(高 5 宽 2, index 2-3)。
    //
    // 2. 失败 / 未命中
    //    检查：空间不是 O(1),栈最坏 O(n)。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC85 最大矩形；LC42 接雨水
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意heights=[2,1,5,6,2,3],城市天际线最大广告牌面积。
2. 2重复为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
3. 3优化单调递增栈存等待右边界的下标;遇更矮柱弹栈,rightLess=i,leftLess=新栈顶,width=i-leftLess-1;末尾 append 0 哨兵清算。
4. 4证明栈里放的是还在等待右边第一个更矮柱子的下标,栈内高度单调递增。；弹栈时 rightLess=当前 i,leftLess=弹栈后栈顶,width=i-leftLess-1。
5. 5复杂度时间 O(n)，空间 O(n)