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 histograms 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 }逐段拆解这段代码代码片段作用n : len(heights) 2逻辑数组比原数组多 2 个位置首尾各 1 个哨兵getHeight(i)闭包对下标0和n-1返回高度 0其余返回heights[i-1]实现逻辑上的哨兵数组而无需真实拷贝内存st : make([]int, 0, n/2)栈中只存下标而非高度值并预分配容量减少扩容内层for弹出循环只要新高度小于栈顶高度就弹出栈顶idx此时idx的矩形左右边界已确定getHeight(idx)*(i-st[len(st)-1]-1)面积 弹出柱子的高度 ×右边界i− 左边界st[len(st)-1]− 1maxArea max(maxArea, ...)每弹出一根柱子就更新一次全局最大值哨兵的两个关键作用左侧哨兵下标 0保证栈永远不会被弹空。当弹出最后一根真实柱子后新的栈顶是下标 0高度 0i - 0 - 1依然能算出正确宽度避免了“栈空时宽度如何取值”的特判。右侧哨兵下标 n-1高度为 0 的哨兵比任何真实柱子的高度都小遍历到最后必然触发对所有剩余柱子的弹出从而保证栈中所有柱子最终都会被结算面积不会漏算递增序列的情况。从源码结构看这种“哨兵化”处理把繁琐的边界分支收敛成了统一的弹出逻辑这也是原文档解题思路中“取出当前最大栈顶的前一个元素……宽就是最后一个比当前下标大的高度和当前下标 i 的差值”所描述过程的机械化落地。手推演算以 [2,1,5,6,2,3] 为例为便于对照下面用“逻辑下标”说明0 和 7 为哨兵真实柱子对应逻辑下标 16高度分别为 2、1、5、6、2、3。i0栈空压入[0]。i1高度 1栈顶高度 2 1弹出下标 0此时st弹空i - 0 - 1 0面积为2 × 0 0随后压入[1]。i2高度 55 1直接压入栈[1,2]。i3高度 66 5直接压入栈[1,2,3]。i4高度 2栈顶高度 6 2弹出下标 3左边界为新的栈顶下标 2宽度4-2-11面积6×16接着栈顶高度 5 2弹出下标 2左边界为下标 1宽度4-1-12面积5×210此时maxArea更新为 10栈顶高度 1 2停止弹出压入下标 4栈[1,4]。i5高度 33 2压入栈[1,4,5]。i6高度 2栈顶高度 3 2弹出下标 5左边界下标 4宽度6-4-11面积3×13栈顶高度 2 与当前高度 2 相等不满足条件严格大于才弹出压入下标 6栈[1,4,6]。i7右侧哨兵高度 0依次弹出下标 6面积2×12、下标 4面积2×48、下标 1面积1×66全部弹出后遍历结束。最终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 个用例很有代表性分别验证输入期望输出覆盖的边界场景[2,1,5,6,2,3]10题目标准示例验证多柱子共同撑起矩形5×2[1]1单根柱子验证最小规模输入[1,1]2高度相等的连续柱子验证相等高度不弹出的处理[2,1,2]3两头高中间低验证栈被弹出后宽度计算的正确性2×1与1×3取最大测试运行方式与仓库其他题目一致在仓库根目录执行go test ./leetcode/0084.Largest-Rectangle-in-Histogram/ -v -run Test_Problem84单调栈解题模板与同族题目从本题可以提炼出单调栈的标准套路确定单调方向求“左右第一个更小元素”用单调递增栈求“左右第一个更大元素”用单调递减栈明确入栈内容通常存下标而非值宽度计算依赖下标差在弹出时结算答案元素被弹出即意味着它的左右边界都已确定此时完成针对它的计算善用哨兵在逻辑数组首尾补一个极端值消除空栈与遍历结束后的残留结算问题。仓库 README_zh.md 指出与本题同属单调栈一族的还有456132 模式、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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 histograms 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 }逐段拆解这段代码代码片段作用n : len(heights) 2逻辑数组比原数组多 2 个位置首尾各 1 个哨兵getHeight(i)闭包对下标0和n-1返回高度 0其余返回heights[i-1]实现逻辑上的哨兵数组而无需真实拷贝内存st : make([]int, 0, n/2)栈中只存下标而非高度值并预分配容量减少扩容内层for弹出循环只要新高度小于栈顶高度就弹出栈顶idx此时idx的矩形左右边界已确定getHeight(idx)*(i-st[len(st)-1]-1)面积 弹出柱子的高度 ×右边界i− 左边界st[len(st)-1]− 1maxArea max(maxArea, ...)每弹出一根柱子就更新一次全局最大值哨兵的两个关键作用左侧哨兵下标 0保证栈永远不会被弹空。当弹出最后一根真实柱子后新的栈顶是下标 0高度 0i - 0 - 1依然能算出正确宽度避免了“栈空时宽度如何取值”的特判。右侧哨兵下标 n-1高度为 0 的哨兵比任何真实柱子的高度都小遍历到最后必然触发对所有剩余柱子的弹出从而保证栈中所有柱子最终都会被结算面积不会漏算递增序列的情况。从源码结构看这种“哨兵化”处理把繁琐的边界分支收敛成了统一的弹出逻辑这也是原文档解题思路中“取出当前最大栈顶的前一个元素……宽就是最后一个比当前下标大的高度和当前下标 i 的差值”所描述过程的机械化落地。手推演算以 [2,1,5,6,2,3] 为例为便于对照下面用“逻辑下标”说明0 和 7 为哨兵真实柱子对应逻辑下标 16高度分别为 2、1、5、6、2、3。i0栈空压入[0]。i1高度 1栈顶高度 2 1弹出下标 0此时st弹空i - 0 - 1 0面积为2 × 0 0随后压入[1]。i2高度 55 1直接压入栈[1,2]。i3高度 66 5直接压入栈[1,2,3]。i4高度 2栈顶高度 6 2弹出下标 3左边界为新的栈顶下标 2宽度4-2-11面积6×16接着栈顶高度 5 2弹出下标 2左边界为下标 1宽度4-1-12面积5×210此时maxArea更新为 10栈顶高度 1 2停止弹出压入下标 4栈[1,4]。i5高度 33 2压入栈[1,4,5]。i6高度 2栈顶高度 3 2弹出下标 5左边界下标 4宽度6-4-11面积3×13栈顶高度 2 与当前高度 2 相等不满足条件严格大于才弹出压入下标 6栈[1,4,6]。i7右侧哨兵高度 0依次弹出下标 6面积2×12、下标 4面积2×48、下标 1面积1×66全部弹出后遍历结束。最终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 个用例很有代表性分别验证输入期望输出覆盖的边界场景[2,1,5,6,2,3]10题目标准示例验证多柱子共同撑起矩形5×2[1]1单根柱子验证最小规模输入[1,1]2高度相等的连续柱子验证相等高度不弹出的处理[2,1,2]3两头高中间低验证栈被弹出后宽度计算的正确性2×1与1×3取最大测试运行方式与仓库其他题目一致在仓库根目录执行go test ./leetcode/0084.Largest-Rectangle-in-Histogram/ -v -run Test_Problem84单调栈解题模板与同族题目从本题可以提炼出单调栈的标准套路确定单调方向求“左右第一个更小元素”用单调递增栈求“左右第一个更大元素”用单调递减栈明确入栈内容通常存下标而非值宽度计算依赖下标差在弹出时结算答案元素被弹出即意味着它的左右边界都已确定此时完成针对它的计算善用哨兵在逻辑数组首尾补一个极端值消除空栈与遍历结束后的残留结算问题。仓库 README_zh.md 指出与本题同属单调栈一族的还有456132 模式、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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考