LeetCode 84 Largest Rectangle in Histogram 直方图中最大矩形从暴力到单调栈的五种解法与多语言源码详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文以 LeetCode 84「Largest Rectangle in Histogram直方图中最大的矩形」为核心系统讲解从 O(n²) 暴力枚举、O(n log n) 分治 线段树到 O(n) 单调栈的完整解法演进路径。仓库 articles/largest-rectangle-in-histogram.md 提供了覆盖 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 等 10 种语言的完整实现并在 python/0084-largest-rectangle-in-histogram.py、cpp/0084-largest-rectangle-in-histogram.cpp 等源码文件中给出可直接运行的参考实现。读完本文你将掌握以每个柱子为高度枚举矩形的建模思路、四种栈式写法的边界差异以及如何用单调栈把该类问题稳定做到 O(n)。问题定义与前置知识给定一个整数数组heights其中每个元素代表直方图中一根柱子的高度柱子的宽度均为 1。要求返回直方图中能勾勒出的最大矩形面积。例如heights [2,1,5,6,2,3]时最大面积为 10对应[2, 3]区间内高度为 5 和 6 的两根柱子见 cpp/0084-largest-rectangle-in-histogram.cpp 的注释示例。在动手解题前需要先熟悉以下基础单调栈Monotonic Stack用栈高效维护元素的递增/递减关系是本题最优解的核心数据结构Next Smaller Element 模式为每个位置找到其左右两侧最近的更小元素这是判断矩形左右边界的关键分治与线段树当需要快速查询任意区间内最小元素的下标时线段树可在 O(log n) 内完成这是解法 2 的加速手段数组遍历在遍历过程中持续维护中间状态如当前最大面积。仓库中的提示文件 hints/largest-rectangle-in-histogram.md 给出了递进式提示先思考以当前柱子的高度作为矩形高度它左右能延伸多远再考虑用单调栈存储下标来预计算左右边界最终目标是 O(n) 时间、O(n) 空间。1. 暴力解法Brute Force直觉对每一根柱子把它当作矩形的最矮柱子。要确定这个矩形能延伸多宽就向左、向右寻找第一根比它矮的柱子作为边界。左右边界之间的宽度就是以该柱子高度为限制的最大矩形宽度。对每根柱子重复该过程并记录最大值即可。算法步骤用maxArea记录当前找到的最大矩形。对每个下标i记height heights[i]为当前柱子高度向右扩展直到遇到高度小于height的柱子向左扩展只要柱子高度不小于height就继续计算左右边界之间的宽度用height * width更新maxArea。返回maxArea。以 Python 为例其余语言版本见下文仓库清单class Solution: def largestRectangleArea(self, heights: List[int]) - int: n len(heights) maxArea 0 for i in range(n): height heights[i] rightMost i 1 while rightMost n and heights[rightMost] height: rightMost 1 leftMost i while leftMost 0 and heights[leftMost] height: leftMost - 1 rightMost - 1 leftMost 1 maxArea max(maxArea, height * (rightMost - leftMost 1)) return maxArea复杂度时间复杂度O(n²)最坏情况下每个柱子都要向两侧扫描接近整个数组空间复杂度O(1)只使用常数个变量。2. 分治 线段树Divide And Conquer with Segment Tree直觉直方图中的任何一个大矩形必然存在某根柱子充当它的最矮柱子。如果在任意区间[L, R]内能快速找到最矮柱子的下标那么以该最矮柱子为限制高度的最大矩形恰好横跨整个区间[L, R]更大的矩形必然完全位于该柱子的左侧或右侧。由此得到分治思路在区间[L, R]中找到最矮柱子的下标minIndex答案取以下三者最大值——横跨全区的面积、完全位于左侧子区间的答案、完全位于右侧子区间的答案。为了快速查询任意区间内最小柱子的下标使用一棵基于 heights 构建的线段树每个节点存储其管辖段内最小高度的下标使区间最小下标查询达到 O(log n)。算法步骤基于 heights 构建线段树每个节点保存该段最小高度的下标定义递归函数solve(L, R)若L R返回 0若L R返回heights[L]只有一根柱子用线段树查出[L, R]内最小柱子的下标minIndex计算area_with_min heights[minIndex] * (R - L 1)、area_left solve(L, minIndex - 1)、area_right solve(minIndex 1, R)返回三者最大值最终答案即solve(0, n - 1)。以 Python 为例线段树用补齐到 2 的幂 迭代建树的方式实现树节点保存的是下标而非值class MinIdx_Segtree: def __init__(self, N, A): self.n N self.INF int(1e9) self.A A while (self.n (self.n - 1)) ! 0: self.A.append(self.INF) self.n 1 self.tree [0] * (2 * self.n) self.build() def build(self): for i in range(self.n): self.tree[self.n i] i for j in range(self.n - 1, 0, -1): a self.tree[j 1] b self.tree[(j 1) 1] if self.A[a] self.A[b]: self.tree[j] a else: self.tree[j] b def update(self, i, val): self.A[i] val j (self.n i) 1 while j 1: a self.tree[j 1] b self.tree[(j 1) 1] if self.A[a] self.A[b]: self.tree[j] a else: self.tree[j] b j 1 def query(self, ql, qh): return self._query(1, 0, self.n - 1, ql, qh) def _query(self, node, l, h, ql, qh): if ql h or qh l: return self.INF if l ql and h qh: return self.tree[node] a self._query(node 1, l, (l h) 1, ql, qh) b self._query((node 1) 1, ((l h) 1) 1, h, ql, qh) if a self.INF: return b if b self.INF: return a return a if self.A[a] self.A[b] else b class Solution: def getMaxArea(self, heights, l, r, st): if l r: return 0 if l r: return heights[l] minIdx st.query(l, r) return max(max(self.getMaxArea(heights, l, minIdx - 1, st), self.getMaxArea(heights, minIdx 1, r, st)), (r - l 1) * heights[minIdx]) def largestRectangleArea(self, heights): n len(heights) st MinIdx_Segtree(n, heights) return self.getMaxArea(heights, 0, n - 1, st)实现细节说明补齐到 2 的幂while (n (n - 1)) ! 0不断追加INF哨兵把数组长度补齐为 2 的幂这样线段树可用2 * n的数组迭代建树避免递归建树哨兵 INF在查询递归中完全不相交的区间返回INF下标表示该侧不存在有效下标父节点据此取另一侧结果节点存下标而非值比较时用A[a] A[b]决定保留哪个下标相等时取左侧下标保证结果确定。复杂度时间复杂度O(n log n)每层递归做一次 O(log n) 的区间最小查询空间复杂度O(n)线段树占用 O(n) 空间递归深度 O(log n)。3. 单调栈两次扫描Stack, Two Pass直觉对每根柱子我们想知道它在碰到更矮柱子之前左右最多能延伸多远这段距离决定了以它为最矮柱子的最大矩形宽度。为了高效地找到两侧最近更小元素使用单调递增栈维护柱子的下标从而在线性时间内算出每个位置的左右边界而不是对每根柱子向外逐个检查。算法步骤用单调栈为每个下标i找左侧最近的更矮柱子若当前柱子比栈顶柱子矮则不断出栈直到不再满足此时栈顶即左边界若栈为空说明左侧没有更矮柱子左边界记为-1从右向左重复同样的过程找右侧最近的更矮柱子若不存在则右边界记为n对每根柱子计算heights[i] * (right - left - 1)取最大值返回。以 Python 为例class Solution: def largestRectangleArea(self, heights: List[int]) - int: n len(heights) stack [] leftMost [-1] * n for i in range(n): while stack and heights[stack[-1]] heights[i]: stack.pop() if stack: leftMost[i] stack[-1] stack.append(i) stack [] rightMost [n] * n for i in range(n - 1, -1, -1): while stack and heights[stack[-1]] heights[i]: stack.pop() if stack: rightMost[i] stack[-1] stack.append(i) maxArea 0 for i in range(n): leftMost[i] 1 rightMost[i] - 1 maxArea max(maxArea, heights[i] * (rightMost[i] - leftMost[i] 1)) return maxArea注意左右边界是开区间记录的是更矮柱子的下标所以最终宽度用rightMost[i] - leftMost[i] 1等价于(right - 1) - (left 1) 1。该版本中相等高度用出栈保证相同高度的柱子能取到最靠左/最靠右的边界结果一致。复杂度时间复杂度O(n)每根柱子至多入栈、出栈一次空间复杂度O(n)栈与两个边界数组各占用 O(n) 空间。4. 单调栈单次扫描Stack, One Pass直觉我们希望为每根柱子找到它能充当最矮柱子的最大宽度。借助单调栈可以在一趟遍历中就地完成栈中保存的是高度递增的柱子每个元素附带该高度最早可以从哪个下标开始的起始位置当遇到一根更矮的新柱子时说明栈顶的较高柱子无法再向右延伸此时弹出并计算它能覆盖的面积新柱子可以向左延伸到被弹出柱子的起始位置因此复用该下标作为自己的start遍历结束后栈中剩余的柱子统一按延伸到数组末尾计算面积。每根柱子至多入栈、出栈各一次因此这是单趟 O(n) 的简洁实现。算法步骤初始化空栈元素为(start_index, height)二元组与maxArea 0从左到右遍历对下标i、高度h令start i当栈非空且栈顶高度大于h时弹出(index, height)用height * (i - index)更新maxArea并令start index新柱子可从被弹出柱子的起点开始将(start, h)入栈遍历结束后处理栈中剩余元素对每个(index, height)用height * (n - index)更新maxArean 为柱子总数返回maxArea。以 Python 为例class Solution: def largestRectangleArea(self, heights: List[int]) - int: maxArea 0 stack [] # pair: (index, height) for i, h in enumerate(heights): start i while stack and stack[-1][1] h: index, height stack.pop() maxArea max(maxArea, height * (i - index)) start index stack.append((start, h)) for i, h in stack: maxArea max(maxArea, h * (len(heights) - i)) return maxArea仓库源码对照该解法正是仓库中多语言参考实现采用的主流写法可以逐行对照验证python/0084-largest-rectangle-in-histogram.py与上文 Python 实现完全一致入栈(start, h)二元组主循环用弹出收尾用h * (len(heights) - i)cpp/0084-largest-rectangle-in-histogram.cppC 版本用stackpairint, int stk存(index, height)主循环stk.top().second heights[i]弹出并计算height * (i - index)收尾循环计算heights.size() - stk.top().first注释明确标注Monotonic incr stack, if curr height lower extend back, find max areajava/0084-largest-rectangle-in-histogram.javaJava 版用StackPairInteger, Integer弹出时area max(area, h * (i - index))收尾用h * (n - index)go/0084-largest-rectangle-in-histogram.goGo 版定义StackValue{index, height}结构体切片作为栈弹出时maxArea max(maxArea, height*(i-index))收尾h.height*(len(heights)-h.index)rust/0084-largest-rectangle-in-histogram.rsRust 版换了一种等价写法——在数组首尾各补一个高度 0 的哨兵栈存下标弹出时宽度为i - stack[stack.len() - 1] - 1本质与 one-pass 思路一致。仓库中还提供了 c/0084-largest-rectangle-in-histogram.c、csharp/0084-largest-rectangle-in-histogram.cs、javascript/0084-largest-rectangle-in-histogram.js、kotlin/0084-largest-rectangle-in-histogram.kt、swift/0084-largest-rectangle-in-histogram.swift、typescript/0084-largest-rectangle-in-histogram.ts、ruby/0084-largest-rectangle-in-histogram.rb 等多个语言版本可对比同一思路在不同语言下的写法差异。复杂度时间复杂度O(n)空间复杂度O(n)。5. 单调栈最优写法Stack, Optimal虚拟高度 0 收尾直觉我们要为每根柱子求出在它仍然作为最矮柱子的前提下能向左右延伸多宽。维护一个高度严格递增的下标栈只要下一根柱子不低于栈顶就持续入栈一旦遇到更矮的柱子说明栈顶柱子无法再向右延伸此时弹出它并以它的高度作为矩形高度宽度从新栈顶下标 1 一直延伸到当前下标 − 1为了让每根柱子最终都能被弹出处理循环额外多走一步在末尾虚拟一根高度为 0 的柱子。每根柱子至多入栈、出栈一次因此这是既最优又干净的写法。算法步骤初始化maxArea 0空栈存下标栈中高度严格递增循环i从0到n含 n只要栈非空且满足i n已越过最后一根柱子等价于高度 0或heights[i] 栈顶下标对应高度弹出栈顶下标记其高度为h计算宽度若栈为空宽度 i从 0 延伸到i - 1否则宽度 i - 新栈顶 - 1用h * width更新maxArea将当前下标i入栈循环结束后maxArea即答案。以 Python 为例class Solution: def largestRectangleArea(self, heights: List[int]) - int: n len(heights) maxArea 0 stack [] for i in range(n 1): while stack and (i n or heights[stack[-1]] heights[i]): height heights[stack.pop()] width i if not stack else i - stack[-1] - 1 maxArea max(maxArea, height * width) stack.append(i) return maxArea为什么末尾要虚拟一根高度 0 的柱子直方图中存在向右一直没有更矮柱子的单调递增段这些柱子的右边界实际是 n。若循环只走到n - 1它们永远不会被弹出、面积永远不会被计算。让i走到n并视作高度 0就能在循环体内一次性把栈中剩余元素全部弹出结算从而省去像解法 4 那样的收尾循环。复杂度时间复杂度O(n)空间复杂度O(n)。常见陷阱Common Pitfalls宽度计算的 Off-by-One 错误计算矩形宽度时若left和right是最近更矮柱子的下标开区间边界宽度应为right - left - 1。忘记减 1或错误地把边界当成闭区间都会导致面积计算错误。解法 3 中对应的写法是rightMost[i] - leftMost[i] 1其中左右边界各自向内收缩了 1。忘记处理栈中剩余元素遍历完所有柱子后栈中可能仍存有右侧从未遇到更矮柱子的下标这些柱子可以一直延伸到直方图末尾。如果不弹出并处理这些剩余元素会漏掉有效的矩形面积解法 4 的收尾循环、解法 5 的虚拟高度 0 都是为了规避此问题。严格大于 vs 非严格大于比较高度决定是否出栈时使用还是会产生不同的边界效果。使用严格时等高柱子可能错误地残留在栈中导致边界计算错误使用时等高柱子会被弹出从而为相等高度的柱子取到正确边界。具体选择取决于对等高柱子左边界的处理方式两种写法都要保证最终面积一致。空栈处理不当计算左边界时若栈已空说明左侧不存在更矮柱子宽度应从下标 0 延伸到当前位置。若不对空栈做显式判断就直接访问stack[-1]/stack.top()会引发运行时错误或得到错误结果解法 3 用-1哨兵、解法 5 用i if not stack分支来规避。未处理单元素与等高数组单根柱子或所有柱子等高这类边界情况必须正确返回单根柱子应返回其高度本身等高数组应返回height * nn 为柱子数量。上述各解法无需特判即可覆盖这些情况但自己重写时容易在边界条件上出 bug。五种解法对比与仓库检索指引解法核心思想时间复杂度空间复杂度适用场景1. 暴力每根柱子向两侧扩展O(n²)O(1)小规模输入、验证正确性2. 分治 线段树以区间最小柱子为分界递归O(n log n)O(n)理解分治思想、练习线段树区间最值查询3. 单调栈两次扫描预计算左右最近更小元素O(n)O(n)面试主流解法之一直观易懂4. 单调栈单次扫描栈存(start, height)一趟结算O(n)O(n)代码简洁、仓库多语言默认实现5. 单调栈最优虚拟高度 0 收尾单循环O(n)O(n)最干净的 O(n) 写法推荐记忆仓库中 14 个与本题直接相关的文件分布如下可据此对照学习解题思路与提示articles/largest-rectangle-in-histogram.md、hints/largest-rectangle-in-histogram.md参考实现python/0084-largest-rectangle-in-histogram.py、cpp/0084-largest-rectangle-in-histogram.cpp、java/0084-largest-rectangle-in-histogram.java、c/0084-largest-rectangle-in-histogram.c、csharp/0084-largest-rectangle-in-histogram.cs、go/0084-largest-rectangle-in-histogram.go、javascript/0084-largest-rectangle-in-histogram.js、kotlin/0084-largest-rectangle-in-histogram.kt、rust/0084-largest-rectangle-in-histogram.rs、swift/0084-largest-rectangle-in-histogram.swift、typescript/0084-largest-rectangle-in-histogram.ts、ruby/0084-largest-rectangle-in-histogram.rb。延伸本题的最近更小元素建模与单调栈技巧可继续对照仓库中 daily-temperatures.md、trapping-rain-water.md 等文章形成对单调栈系列题型的系统认知。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 84 Largest Rectangle in Histogram 直方图中最大矩形：从暴力到单调栈的五种解法与多语言源码详解
LeetCode 84 Largest Rectangle in Histogram 直方图中最大矩形从暴力到单调栈的五种解法与多语言源码详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文以 LeetCode 84「Largest Rectangle in Histogram直方图中最大的矩形」为核心系统讲解从 O(n²) 暴力枚举、O(n log n) 分治 线段树到 O(n) 单调栈的完整解法演进路径。仓库 articles/largest-rectangle-in-histogram.md 提供了覆盖 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 等 10 种语言的完整实现并在 python/0084-largest-rectangle-in-histogram.py、cpp/0084-largest-rectangle-in-histogram.cpp 等源码文件中给出可直接运行的参考实现。读完本文你将掌握以每个柱子为高度枚举矩形的建模思路、四种栈式写法的边界差异以及如何用单调栈把该类问题稳定做到 O(n)。问题定义与前置知识给定一个整数数组heights其中每个元素代表直方图中一根柱子的高度柱子的宽度均为 1。要求返回直方图中能勾勒出的最大矩形面积。例如heights [2,1,5,6,2,3]时最大面积为 10对应[2, 3]区间内高度为 5 和 6 的两根柱子见 cpp/0084-largest-rectangle-in-histogram.cpp 的注释示例。在动手解题前需要先熟悉以下基础单调栈Monotonic Stack用栈高效维护元素的递增/递减关系是本题最优解的核心数据结构Next Smaller Element 模式为每个位置找到其左右两侧最近的更小元素这是判断矩形左右边界的关键分治与线段树当需要快速查询任意区间内最小元素的下标时线段树可在 O(log n) 内完成这是解法 2 的加速手段数组遍历在遍历过程中持续维护中间状态如当前最大面积。仓库中的提示文件 hints/largest-rectangle-in-histogram.md 给出了递进式提示先思考以当前柱子的高度作为矩形高度它左右能延伸多远再考虑用单调栈存储下标来预计算左右边界最终目标是 O(n) 时间、O(n) 空间。1. 暴力解法Brute Force直觉对每一根柱子把它当作矩形的最矮柱子。要确定这个矩形能延伸多宽就向左、向右寻找第一根比它矮的柱子作为边界。左右边界之间的宽度就是以该柱子高度为限制的最大矩形宽度。对每根柱子重复该过程并记录最大值即可。算法步骤用maxArea记录当前找到的最大矩形。对每个下标i记height heights[i]为当前柱子高度向右扩展直到遇到高度小于height的柱子向左扩展只要柱子高度不小于height就继续计算左右边界之间的宽度用height * width更新maxArea。返回maxArea。以 Python 为例其余语言版本见下文仓库清单class Solution: def largestRectangleArea(self, heights: List[int]) - int: n len(heights) maxArea 0 for i in range(n): height heights[i] rightMost i 1 while rightMost n and heights[rightMost] height: rightMost 1 leftMost i while leftMost 0 and heights[leftMost] height: leftMost - 1 rightMost - 1 leftMost 1 maxArea max(maxArea, height * (rightMost - leftMost 1)) return maxArea复杂度时间复杂度O(n²)最坏情况下每个柱子都要向两侧扫描接近整个数组空间复杂度O(1)只使用常数个变量。2. 分治 线段树Divide And Conquer with Segment Tree直觉直方图中的任何一个大矩形必然存在某根柱子充当它的最矮柱子。如果在任意区间[L, R]内能快速找到最矮柱子的下标那么以该最矮柱子为限制高度的最大矩形恰好横跨整个区间[L, R]更大的矩形必然完全位于该柱子的左侧或右侧。由此得到分治思路在区间[L, R]中找到最矮柱子的下标minIndex答案取以下三者最大值——横跨全区的面积、完全位于左侧子区间的答案、完全位于右侧子区间的答案。为了快速查询任意区间内最小柱子的下标使用一棵基于 heights 构建的线段树每个节点存储其管辖段内最小高度的下标使区间最小下标查询达到 O(log n)。算法步骤基于 heights 构建线段树每个节点保存该段最小高度的下标定义递归函数solve(L, R)若L R返回 0若L R返回heights[L]只有一根柱子用线段树查出[L, R]内最小柱子的下标minIndex计算area_with_min heights[minIndex] * (R - L 1)、area_left solve(L, minIndex - 1)、area_right solve(minIndex 1, R)返回三者最大值最终答案即solve(0, n - 1)。以 Python 为例线段树用补齐到 2 的幂 迭代建树的方式实现树节点保存的是下标而非值class MinIdx_Segtree: def __init__(self, N, A): self.n N self.INF int(1e9) self.A A while (self.n (self.n - 1)) ! 0: self.A.append(self.INF) self.n 1 self.tree [0] * (2 * self.n) self.build() def build(self): for i in range(self.n): self.tree[self.n i] i for j in range(self.n - 1, 0, -1): a self.tree[j 1] b self.tree[(j 1) 1] if self.A[a] self.A[b]: self.tree[j] a else: self.tree[j] b def update(self, i, val): self.A[i] val j (self.n i) 1 while j 1: a self.tree[j 1] b self.tree[(j 1) 1] if self.A[a] self.A[b]: self.tree[j] a else: self.tree[j] b j 1 def query(self, ql, qh): return self._query(1, 0, self.n - 1, ql, qh) def _query(self, node, l, h, ql, qh): if ql h or qh l: return self.INF if l ql and h qh: return self.tree[node] a self._query(node 1, l, (l h) 1, ql, qh) b self._query((node 1) 1, ((l h) 1) 1, h, ql, qh) if a self.INF: return b if b self.INF: return a return a if self.A[a] self.A[b] else b class Solution: def getMaxArea(self, heights, l, r, st): if l r: return 0 if l r: return heights[l] minIdx st.query(l, r) return max(max(self.getMaxArea(heights, l, minIdx - 1, st), self.getMaxArea(heights, minIdx 1, r, st)), (r - l 1) * heights[minIdx]) def largestRectangleArea(self, heights): n len(heights) st MinIdx_Segtree(n, heights) return self.getMaxArea(heights, 0, n - 1, st)实现细节说明补齐到 2 的幂while (n (n - 1)) ! 0不断追加INF哨兵把数组长度补齐为 2 的幂这样线段树可用2 * n的数组迭代建树避免递归建树哨兵 INF在查询递归中完全不相交的区间返回INF下标表示该侧不存在有效下标父节点据此取另一侧结果节点存下标而非值比较时用A[a] A[b]决定保留哪个下标相等时取左侧下标保证结果确定。复杂度时间复杂度O(n log n)每层递归做一次 O(log n) 的区间最小查询空间复杂度O(n)线段树占用 O(n) 空间递归深度 O(log n)。3. 单调栈两次扫描Stack, Two Pass直觉对每根柱子我们想知道它在碰到更矮柱子之前左右最多能延伸多远这段距离决定了以它为最矮柱子的最大矩形宽度。为了高效地找到两侧最近更小元素使用单调递增栈维护柱子的下标从而在线性时间内算出每个位置的左右边界而不是对每根柱子向外逐个检查。算法步骤用单调栈为每个下标i找左侧最近的更矮柱子若当前柱子比栈顶柱子矮则不断出栈直到不再满足此时栈顶即左边界若栈为空说明左侧没有更矮柱子左边界记为-1从右向左重复同样的过程找右侧最近的更矮柱子若不存在则右边界记为n对每根柱子计算heights[i] * (right - left - 1)取最大值返回。以 Python 为例class Solution: def largestRectangleArea(self, heights: List[int]) - int: n len(heights) stack [] leftMost [-1] * n for i in range(n): while stack and heights[stack[-1]] heights[i]: stack.pop() if stack: leftMost[i] stack[-1] stack.append(i) stack [] rightMost [n] * n for i in range(n - 1, -1, -1): while stack and heights[stack[-1]] heights[i]: stack.pop() if stack: rightMost[i] stack[-1] stack.append(i) maxArea 0 for i in range(n): leftMost[i] 1 rightMost[i] - 1 maxArea max(maxArea, heights[i] * (rightMost[i] - leftMost[i] 1)) return maxArea注意左右边界是开区间记录的是更矮柱子的下标所以最终宽度用rightMost[i] - leftMost[i] 1等价于(right - 1) - (left 1) 1。该版本中相等高度用出栈保证相同高度的柱子能取到最靠左/最靠右的边界结果一致。复杂度时间复杂度O(n)每根柱子至多入栈、出栈一次空间复杂度O(n)栈与两个边界数组各占用 O(n) 空间。4. 单调栈单次扫描Stack, One Pass直觉我们希望为每根柱子找到它能充当最矮柱子的最大宽度。借助单调栈可以在一趟遍历中就地完成栈中保存的是高度递增的柱子每个元素附带该高度最早可以从哪个下标开始的起始位置当遇到一根更矮的新柱子时说明栈顶的较高柱子无法再向右延伸此时弹出并计算它能覆盖的面积新柱子可以向左延伸到被弹出柱子的起始位置因此复用该下标作为自己的start遍历结束后栈中剩余的柱子统一按延伸到数组末尾计算面积。每根柱子至多入栈、出栈各一次因此这是单趟 O(n) 的简洁实现。算法步骤初始化空栈元素为(start_index, height)二元组与maxArea 0从左到右遍历对下标i、高度h令start i当栈非空且栈顶高度大于h时弹出(index, height)用height * (i - index)更新maxArea并令start index新柱子可从被弹出柱子的起点开始将(start, h)入栈遍历结束后处理栈中剩余元素对每个(index, height)用height * (n - index)更新maxArean 为柱子总数返回maxArea。以 Python 为例class Solution: def largestRectangleArea(self, heights: List[int]) - int: maxArea 0 stack [] # pair: (index, height) for i, h in enumerate(heights): start i while stack and stack[-1][1] h: index, height stack.pop() maxArea max(maxArea, height * (i - index)) start index stack.append((start, h)) for i, h in stack: maxArea max(maxArea, h * (len(heights) - i)) return maxArea仓库源码对照该解法正是仓库中多语言参考实现采用的主流写法可以逐行对照验证python/0084-largest-rectangle-in-histogram.py与上文 Python 实现完全一致入栈(start, h)二元组主循环用弹出收尾用h * (len(heights) - i)cpp/0084-largest-rectangle-in-histogram.cppC 版本用stackpairint, int stk存(index, height)主循环stk.top().second heights[i]弹出并计算height * (i - index)收尾循环计算heights.size() - stk.top().first注释明确标注Monotonic incr stack, if curr height lower extend back, find max areajava/0084-largest-rectangle-in-histogram.javaJava 版用StackPairInteger, Integer弹出时area max(area, h * (i - index))收尾用h * (n - index)go/0084-largest-rectangle-in-histogram.goGo 版定义StackValue{index, height}结构体切片作为栈弹出时maxArea max(maxArea, height*(i-index))收尾h.height*(len(heights)-h.index)rust/0084-largest-rectangle-in-histogram.rsRust 版换了一种等价写法——在数组首尾各补一个高度 0 的哨兵栈存下标弹出时宽度为i - stack[stack.len() - 1] - 1本质与 one-pass 思路一致。仓库中还提供了 c/0084-largest-rectangle-in-histogram.c、csharp/0084-largest-rectangle-in-histogram.cs、javascript/0084-largest-rectangle-in-histogram.js、kotlin/0084-largest-rectangle-in-histogram.kt、swift/0084-largest-rectangle-in-histogram.swift、typescript/0084-largest-rectangle-in-histogram.ts、ruby/0084-largest-rectangle-in-histogram.rb 等多个语言版本可对比同一思路在不同语言下的写法差异。复杂度时间复杂度O(n)空间复杂度O(n)。5. 单调栈最优写法Stack, Optimal虚拟高度 0 收尾直觉我们要为每根柱子求出在它仍然作为最矮柱子的前提下能向左右延伸多宽。维护一个高度严格递增的下标栈只要下一根柱子不低于栈顶就持续入栈一旦遇到更矮的柱子说明栈顶柱子无法再向右延伸此时弹出它并以它的高度作为矩形高度宽度从新栈顶下标 1 一直延伸到当前下标 − 1为了让每根柱子最终都能被弹出处理循环额外多走一步在末尾虚拟一根高度为 0 的柱子。每根柱子至多入栈、出栈一次因此这是既最优又干净的写法。算法步骤初始化maxArea 0空栈存下标栈中高度严格递增循环i从0到n含 n只要栈非空且满足i n已越过最后一根柱子等价于高度 0或heights[i] 栈顶下标对应高度弹出栈顶下标记其高度为h计算宽度若栈为空宽度 i从 0 延伸到i - 1否则宽度 i - 新栈顶 - 1用h * width更新maxArea将当前下标i入栈循环结束后maxArea即答案。以 Python 为例class Solution: def largestRectangleArea(self, heights: List[int]) - int: n len(heights) maxArea 0 stack [] for i in range(n 1): while stack and (i n or heights[stack[-1]] heights[i]): height heights[stack.pop()] width i if not stack else i - stack[-1] - 1 maxArea max(maxArea, height * width) stack.append(i) return maxArea为什么末尾要虚拟一根高度 0 的柱子直方图中存在向右一直没有更矮柱子的单调递增段这些柱子的右边界实际是 n。若循环只走到n - 1它们永远不会被弹出、面积永远不会被计算。让i走到n并视作高度 0就能在循环体内一次性把栈中剩余元素全部弹出结算从而省去像解法 4 那样的收尾循环。复杂度时间复杂度O(n)空间复杂度O(n)。常见陷阱Common Pitfalls宽度计算的 Off-by-One 错误计算矩形宽度时若left和right是最近更矮柱子的下标开区间边界宽度应为right - left - 1。忘记减 1或错误地把边界当成闭区间都会导致面积计算错误。解法 3 中对应的写法是rightMost[i] - leftMost[i] 1其中左右边界各自向内收缩了 1。忘记处理栈中剩余元素遍历完所有柱子后栈中可能仍存有右侧从未遇到更矮柱子的下标这些柱子可以一直延伸到直方图末尾。如果不弹出并处理这些剩余元素会漏掉有效的矩形面积解法 4 的收尾循环、解法 5 的虚拟高度 0 都是为了规避此问题。严格大于 vs 非严格大于比较高度决定是否出栈时使用还是会产生不同的边界效果。使用严格时等高柱子可能错误地残留在栈中导致边界计算错误使用时等高柱子会被弹出从而为相等高度的柱子取到正确边界。具体选择取决于对等高柱子左边界的处理方式两种写法都要保证最终面积一致。空栈处理不当计算左边界时若栈已空说明左侧不存在更矮柱子宽度应从下标 0 延伸到当前位置。若不对空栈做显式判断就直接访问stack[-1]/stack.top()会引发运行时错误或得到错误结果解法 3 用-1哨兵、解法 5 用i if not stack分支来规避。未处理单元素与等高数组单根柱子或所有柱子等高这类边界情况必须正确返回单根柱子应返回其高度本身等高数组应返回height * nn 为柱子数量。上述各解法无需特判即可覆盖这些情况但自己重写时容易在边界条件上出 bug。五种解法对比与仓库检索指引解法核心思想时间复杂度空间复杂度适用场景1. 暴力每根柱子向两侧扩展O(n²)O(1)小规模输入、验证正确性2. 分治 线段树以区间最小柱子为分界递归O(n log n)O(n)理解分治思想、练习线段树区间最值查询3. 单调栈两次扫描预计算左右最近更小元素O(n)O(n)面试主流解法之一直观易懂4. 单调栈单次扫描栈存(start, height)一趟结算O(n)O(n)代码简洁、仓库多语言默认实现5. 单调栈最优虚拟高度 0 收尾单循环O(n)O(n)最干净的 O(n) 写法推荐记忆仓库中 14 个与本题直接相关的文件分布如下可据此对照学习解题思路与提示articles/largest-rectangle-in-histogram.md、hints/largest-rectangle-in-histogram.md参考实现python/0084-largest-rectangle-in-histogram.py、cpp/0084-largest-rectangle-in-histogram.cpp、java/0084-largest-rectangle-in-histogram.java、c/0084-largest-rectangle-in-histogram.c、csharp/0084-largest-rectangle-in-histogram.cs、go/0084-largest-rectangle-in-histogram.go、javascript/0084-largest-rectangle-in-histogram.js、kotlin/0084-largest-rectangle-in-histogram.kt、rust/0084-largest-rectangle-in-histogram.rs、swift/0084-largest-rectangle-in-histogram.swift、typescript/0084-largest-rectangle-in-histogram.ts、ruby/0084-largest-rectangle-in-histogram.rb。延伸本题的最近更小元素建模与单调栈技巧可继续对照仓库中 daily-temperatures.md、trapping-rain-water.md 等文章形成对单调栈系列题型的系统认知。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考