LeetCode 84（柱状图中最大的矩形）是一道著名的 Hard，也是「单调栈」这个技巧最标准的教科书案例：给定一个柱状图（数组每个元素是柱高、宽度为 1），找出其中能勾勒出的最大矩形面积。它难在两点：暴力思路（枚举每对左右边界，取区间最小高）是 O(n²)，对 10⁵ 量级的输入会超时；而把复杂度压到 O(n) 的单调栈，初见时几乎无法从题面「推导」出来——它更像一个需要先理解、再背熟、最后内化的结构。本文从「限高柱」这个视角重新组织问题，推导出 O(n) 解法，代码本地验证（含三万组随机对拍），最后把单调栈家族的使用心法整理成表。先给一个直觉锚点：这道题的样例答案（高度 5 与 6 的两根柱子拼出面积 10）几乎人人能「看出来」，难的不是看，是说出「看」的规则——本文要做的正是把这份直觉形式化。
一、换个视角：每个矩形都有一根「限高柱」
题目的矩形由连续柱子组成，高度受限于区间内最矮的那根柱子。暴力枚举左右边界是 O(n²)；换一个枚举对象，复杂度立刻有解——枚举「限高柱」：任何矩形必然以某根柱子为最矮柱，那么对每根柱子 i，问一个问题：以 heights[i] 为高，这根柱子能向左右各伸多远？答案明确——伸到左边第一个比它矮的柱子（不含）与右边第一个比它矮的柱子（不含）为止。设这两个位置为 left[i] 与 right[i]，以 i 为限高柱的最大矩形面积就是 heights[i] × (right[i] - left[i] - 1)。
这个视角的妙处值得停一下：它把「在所有区间里找最大」这个指数级的搜索问题，压缩成了「恰好 n 个候选矩形」——因为最优矩形总是被某根柱子顶住（把最优矩形往上加高会碰到更高的邻居、往左右扩会碰到更矮的邻居，所以它必然顶到自己的限高柱）。搜索空间从 O(n²) 个区间塌缩到 n 个候选，剩下的全部工作就是高效求出每根柱子的左右边界。
枚举所有 n 根柱子取最大值，问题解决——前提是能快速求出每根柱子的左右边界。暴力地「向左扫到第一个更矮的」是每根 O(n)，合计仍 O(n²)。真正的一步跨越是意识到：求「每个元素左边第一个更小元素」这类问题，有一个 O(n) 的通用解法——单调栈。它的原理朴素：维护一个栈，从栈底到栈顶的高度严格递增；遇到新柱子时，把栈里所有比它高的柱子弹出——每一次弹出，恰好就是一次「找到了右边界」的事件：被弹出的柱子，它右边第一个更矮的就是当前柱子；而它弹出后的新栈顶，恰好是它左边第一个更矮的。一次遍历，每根柱子入栈一次、出栈一次，所有边界全部求出，总复杂度 O(n)。
用题目自带的示例把整个过程走一遍，节奏就有了画面感。输入 [2, 1, 5, 6, 2, 3]：i=0（高 2）入栈；i=1（高 1）比栈顶矮——弹出 2 号柱（右边界 1、左边界空栈记 -1，宽 1−(−1)−1=1，面积 2），1 入栈；i=2（高 5）与 i=3（高 6）依次入栈，栈内高度 1,5,6 递增；i=4（高 2）到来，连续弹出 6 号柱（右边界 4、左边界 5 号柱，宽 4−2−1=1，面积 6）与 5 号柱（右边界 4、左边界 1 号柱，宽 4−1−1=2，面积 10——这就是答案），2 入栈；i=5（高 3）入栈；遍历结束，栈里残留 1,2,3 号柱，右边界取默认值 n。六根柱子、四次弹出各得一个答案——「每次弹出即一次答案」的节奏就是这样。
二、代码实现（Python，本地验证通过）
class Solution:
def largestRectangleArea(self, heights: list[int]) -> int:
n = len(heights)
stack = [] # 存索引，栈内高度递增
left = [-1] * n # 左边第一个更矮的位置（不存在则 -1）
right = [n] * n # 右边第一个更矮的位置（不存在则 n）
for i, h in enumerate(heights):
while stack and heights[stack[-1]] >= h:
j = stack.pop()
right[j] = i # 弹出时：i 是 j 的右边界
left[i] = stack[-1] if stack else -1
stack.append(i)
return max(heights[j] * (right[j] - left[j] - 1) for j in range(n))
这段实现有两个必须讲清的边界约定。其一：等高柱怎么办？出栈条件用 >=（遇到等高也弹出）意味着等高柱子中「靠左的」会先被弹出、其右边界记到当前等高柱上——它的算出的宽度偏窄；但等高平台中最右的那根柱子不会被「等高的邻居」弹出，它的右边界正确地伸到平台之外，因此它的面积覆盖了整个等高段——至少有一根柱子替整个平台拿到正确答案，最大值不受影响。这是等高处理的经典约定：不必追求每根柱子的边界都精确，只要求「每一段都被某根柱子正确覆盖」。
其二：栈里为什么存索引而不是高度？高度在弹出时随时可以从数组读回，但宽度计算离不开位置——右边界是当前索引、左边界是弹出后的新栈顶索引，两者都是位置信息。存高度的栈无法回答「这根柱子在哪」，宽度也就无从算起。「栈里存什么」这类设计选择，判据永远是：算答案时需要哪些信息，就把哪些信息留在栈里。
还有一处工程细节值得点出：这看似双层的 while 循环，总复杂度为什么是 O(n) 而不是 O(n²)？答案是摊还分析——每根柱子的生命周期是「入栈一次、出栈一次」，弹出的总次数被入栈的总次数封顶；while 循环的全部工作量摊到 n 次入栈上，每次摊还 O(1)。「嵌套循环未必平方」是单调栈给初学者上的最重要一课，同样的摊还论证日后还会出现在并查集、KMP 等一系列结构里。
其二：哨兵技巧。遍历结束后栈里会残留一段递增的柱子（它们右边没有更矮的），需要单独收尾。更优雅的做法是在数组末尾追加一个高度为 0 的哨兵柱——所有真实柱子都比它高，循环走完时哨兵会把整条栈弹空，收尾逻辑自然并入主循环。本文的实现选择的是显式的 right[j] = n 默认值方案，效果等价：不存在右边界时，矩形向右伸到数组尽头。
三、本地验证：对拍 30000 组
正确性靠证明，可用性靠验证。按约束（1 <= heights.length <= 10^5、0 <= heights[i] <= 10^4）做两层测试：手工边界（全同高度、严格递增、严格递减、含零高度柱、单根柱）；以及随机对拍——与「枚举每根柱子为限高柱、向左右暴力扩展」的 O(n²) 参考实现对跑，固定随机种子 30000 组（长度 1–60、含零与等高平台），逐组断言面积一致。发布前本地运行：
手工边界通过；30000 组对拍全部一致
对拍在这道题上的针对性极强：等高柱的边界约定、含零柱的宽度计算、栈清空时机——这些地方的错误在手工用例里极难暴露（答案常常「碰巧」对，因为最大矩形来自别的柱子），而随机对拍会在某个带等高平台与零柱共存的组合里把它们揪出来。
四、单调整数栈心法：一张使用地图
把这道题的方法论抽象出来，单调栈的适用场景有一个统一的形状：对每个元素，求「左/右第一个比它大（或小）的元素」。凡是问题能翻译成这个形状的，都是单调栈的地盘——柱状图最大矩形（本题，求左右更矮）、每日温度（求右侧第一个更高）、下一个更大元素（右侧更大）、接雨水（也可用左右最大值的思路，与单调栈解法殊途同归）。本站此前的《LeetCode 42. 接雨水》讲过「每根柱子上方能积多少水」的解法，它与本题共享同一片直觉土壤——都是围绕「每根柱子在左右邻居约束下的能力边界」做文章，放在一起对照读，单调栈的两种用法（直接求边界 / 求边界后积分）就都齐了。心法可以收成三条：栈里维护的是「尚未找到答案的元素」——它们都在等一个「把它弹出来」的时机；弹出的时机就是获得答案的时机——新元素与栈顶的关系一确定，被弹者的某侧边界立刻可知；单调方向由问题决定——求「第一个更小」用递增栈，求「第一个更大」用递减栈，把「出栈条件是 > 还是 >=」与等高约定一起想清楚，边界就不会翻车。
辨析一个初学者常见的困惑作为收束：为什么弹出时的判断标准是「当前柱更矮」，而不是「当前柱更矮或等高就必须二选一纠结」？答案藏在问题的结构里——等高柱子的「左右第一个更矮」本就该指向同一个位置，无论把这个位置记在平台哪一根头上，最终的最大面积都由「至少一根全平台覆盖的柱子」保证。换句话说，等高时的边界归属是不重要的自由度，题目只要最大值，不要求每个候选矩形的归属清晰。识别「哪些精度是题目真正需要的」，是 Hard 题与简单题在思维方式上的真正分野。
最后一提工程上的小优化与延伸：如果只需要最大面积而不需要每根柱子的边界，left/right 两个数组都可以省掉——在弹出被弹柱的瞬间就地计算面积（右边界是当前 i，左边界是弹出后的新栈顶），一次遍历一个栈收工；本文为了讲解清晰保留了显式数组。这道题还有一个著名的二维延伸（矩阵中的最大矩形，把每一行看作柱状图的底、逐行压栈），思路正是「把二维问题降维成多次本题」——学会 84，等于同时解锁了它的家族。
结语
柱状图最大矩形的价值，在于它示范了一次完整的复杂度跃迁：从「枚举边界」到「枚举限高柱」是视角转换（问题没变，枚举对象变了），从「每根暴力扫」到「单调栈批量求边界」是结构利用（有序性藏在遍历顺序里）。这道题之所以是单调栈的第一课，是因为它把这个结构用到最典型的地方——每一个弹出事件都精确对应一个答案。理解了「栈里留的是没等到答案的元素」，单调栈的家族题目都会变得可推导，而不是可背诵。
读者留言
COMMENTS 暂无还没有留言，来说第一句？