LeetCode-Go 题解：84. Largest Rectangle in Histogram 柱状图中最大的矩形 —— 单调栈边界推演与哨兵优化

LeetCode-Go 题解：84. Largest Rectangle in Histogram 柱状图中最大的矩形 —— 单调栈边界推演与哨兵优化

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文基于 LeetCode-Go 仓库中 LeetCode 84 题官方题解文档 及其配套 Go 源码与单元测试，系统讲解“柱状图中最大的矩形”这一经典栈应用问题。你将掌握单调栈（Monotonic Stack）的核心思想、左右边界如何通过下标差精确求出、以及仓库实现中首尾“哨兵”技巧为何能让代码大幅简化；读完即可独立写出O(n)时间、O(n)空间的 Go 解法，并能迁移到 456、496、503、739、901、907、1019 等同族题目。

题目背景与题意

LeetCode 84 是栈专题中最具代表性的 Hard 题之一，在仓库 README_zh.md 的 Stack 章节 中被归入单调栈一类：“利用栈维护一个单调递增或者递减的下标数组”。

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

给定n个非负整数，表示直方图中每根柱子的高度，每根柱子的宽度为 1。要求在直方图中找到面积最大的矩形并输出其面积。关键限制是：矩形必须完全包含在直方图轮廓之内，不能悬空。

以题目标准示例为例，给定高度数组height = [2,1,5,6,2,3]，直方图形态如下：

█ █ █ █ █ █ █ ▄ █ █ ▄ █ ▄ █ █ █ █ █ █ 2 1 5 6 2 3

面积最大的矩形由第 3、4 根柱子（高度 5 和 6）共同撑起，高度取两者中较小的 5，宽度为 2，面积为5 × 2 = 10。示例输入输出：

Input: [2,1,5,6,2,3] Output: 10

题目大意

给出每个直方图的高度，要求在这些直方图之中找到面积最大的矩形，输出矩形的面积。直观地说：任取一段连续的柱子区间[l, r]，这段区间能形成的最大矩形高度是该区间内的最小高度，宽度是r - l + 1，因此矩形面积等于区间最小高度 × 区间宽度。问题等价于：对每一根柱子，找到它作为“最低高度”时能向左右延伸的最远距离，从而枚举出所有候选矩形。

从暴力枚举到单调栈

朴素思路：枚举区间

最直接的做法是枚举所有O(n²)个柱子区间，对每个区间求最小高度，总时间复杂度O(n³)，即便用前缀/线段树优化最小高度查询也仍为O(n²)，在n达到10⁵级别时完全不可行。

换一个角度：以每根柱子为矩形的高

把问题翻转过来：对第i根柱子，假设它所在矩形的高度就是heights[i]（矩形高度由最矮的柱子决定），那么这个矩形能向左延伸到“左边第一根高度小于heights[i]的柱子之后”，向右延伸到“右边第一根高度小于heights[i]的柱子之后”。如果能对每根柱子快速求出左右两个边界，就能在O(n)时间内枚举出所有候选矩形面积并取最大值。

这正是单调栈的用武之地：用栈维护一个高度单调递增的下标序列，保证栈内下标对应的高度自底向上严格递增。当新元素破坏了单调性时，栈顶元素作为“被弹出的高柱子”，它的左边界就是弹出后新的栈顶下标，右边界就是当前遍历到的下标——两边界之间夹着的，正是以它为高的最大矩形。

仓库源码实现：单调栈 + 首尾哨兵

LeetCode-Go 仓库在 84. Largest Rectangle in Histogram.go 中给出了完整实现，其精妙之处在于通过在数组首尾各插入一个高度为 0 的“哨兵”，免去了所有边界判断：

package leetcode 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 }

逐段拆解这段代码：

哨兵的两个关键作用

1. 左侧哨兵（下标 0）：保证栈永远不会被弹空。当弹出最后一根真实柱子后，新的栈顶是下标 0（高度 0），i - 0 - 1依然能算出正确宽度，避免了“栈空时宽度如何取值”的特判。
2. 右侧哨兵（下标 n-1）：高度为 0 的哨兵比任何真实柱子的高度都小，遍历到最后必然触发对所有剩余柱子的弹出，从而保证栈中所有柱子最终都会被结算面积，不会漏算递增序列的情况。

从源码结构看，这种“哨兵化”处理把繁琐的边界分支收敛成了统一的弹出逻辑，这也是原文档解题思路中“取出当前最大栈顶的前一个元素……宽就是最后一个比当前下标大的高度和当前下标 i 的差值”所描述过程的机械化落地。

手推演算：以 [2,1,5,6,2,3] 为例

为便于对照，下面用“逻辑下标”说明（0 和 7 为哨兵，真实柱子对应逻辑下标 1～6，高度分别为 2、1、5、6、2、3）。

1. i=0：栈空，压入[0]。
2. i=1（高度 1）：栈顶高度 2 > 1，弹出下标 0，此时st弹空，i - 0 - 1 = 0，面积为2 × 0 = 0；随后压入[1]。
3. i=2（高度 5）：5 > 1，直接压入，栈[1,2]。
4. i=3（高度 6）：6 > 5，直接压入，栈[1,2,3]。
5. i=4（高度 2）：栈顶高度 6 > 2，弹出下标 3，左边界为新的栈顶下标 2，宽度4-2-1=1，面积6×1=6；接着栈顶高度 5 > 2，弹出下标 2，左边界为下标 1，宽度4-1-1=2，面积5×2=10，此时maxArea更新为 10；栈顶高度 1 < 2，停止弹出，压入下标 4，栈[1,4]。
6. i=5（高度 3）：3 > 2，压入，栈[1,4,5]。
7. i=6（高度 2）：栈顶高度 3 > 2，弹出下标 5，左边界下标 4，宽度6-4-1=1，面积3×1=3；栈顶高度 2 与当前高度 2 相等，不满足>条件（严格大于才弹出），压入下标 6，栈[1,4,6]。
8. i=7（右侧哨兵，高度 0）：依次弹出下标 6（面积2×1=2）、下标 4（面积2×4=8）、下标 1（面积1×6=6），全部弹出后遍历结束。

最终maxArea = 10，与题目输出一致。注意第 7 步中“高度相等时不弹出”保证了相同高度的柱子可以共享同一高度区间、在最左侧那根处才结算完整宽度，这与“单调（不递减）栈”的语义一致。

复杂度分析

• 时间复杂度O(n)：每个下标至多入栈一次、出栈一次，内层循环总执行次数不超过n次，是严格的线性时间。
• 空间复杂度O(n)：栈最多同时保存所有下标（如整体递增序列），因此空间为线性。

作为对比，仓库 README_zh.md 中明确将该题归入单调栈应用，而单调栈的核心价值正是在于以空间换时间——用线性空间把“找左右第一个更小元素”从O(n)摊还到每次O(1)。

单元测试验证

仓库为本题提供了完整测试用例，见 84. Largest Rectangle in Histogram_test.go，共覆盖 4 组输入：

qs := []question84{ {para84{[]int{2, 1, 5, 6, 2, 3}}, ans84{10}}, {para84{[]int{1}}, ans84{1}}, {para84{[]int{1, 1}}, ans84{2}}, {para84{[]int{2, 1, 2}}, ans84{3}}, }

这 4 个用例很有代表性，分别验证：

测试运行方式与仓库其他题目一致，在仓库根目录执行：

go test ./leetcode/0084.Largest-Rectangle-in-Histogram/ -v -run Test_Problem84

单调栈解题模板与同族题目

从本题可以提炼出单调栈的标准套路：

1. 确定单调方向：求“左右第一个更小元素”用单调递增栈，求“左右第一个更大元素”用单调递减栈；
2. 明确入栈内容：通常存下标而非值，宽度计算依赖下标差；
3. 在弹出时结算答案：元素被弹出即意味着它的左右边界都已确定，此时完成针对它的计算；
4. 善用哨兵：在逻辑数组首尾补一个极端值，消除空栈与遍历结束后的残留结算问题。

仓库 README_zh.md 指出，与本题同属单调栈一族的还有456（132 模式）、496（下一个更大元素 I）、503（下一个更大元素 II）、739（每日温度）、901（股票价格跨度）、907（子数组的最小值之和）、1019（链表中的下一个更大节点）等题，解题思路一脉相承，读者可结合这些题目反复练习，巩固“利用栈维护一个单调递增或者递减的下标数组”这一核心思想。

总结

LeetCode 84 通过“枚举每根柱子作为矩形高度 + 单调栈确定左右边界”将暴力O(n³)优化为线性O(n)。LeetCode-Go 仓库的 Go 实现 用首尾两个高度为 0 的哨兵优雅地统一了边界条件，配合 4 组针对性单元测试 覆盖了单柱、等高柱与凹陷序列等关键场景。掌握本题，你便掌握了单调栈这一线性数据结构在“区间最值/边界查询”问题中的核心用法，可直接迁移至仓库中其余 8 道单调栈同族题目。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go