企业官网建设流程全解析

如果你刷题有一阵子了，大概率会在某一天和LeetCode 84“柱状图中最大的矩形”迎头撞上。这题表面风平浪静——给一串宽度为1、高度各异的柱子，求能勾勒出的最大矩形面积，实则暗流涌动。我第一次做的时候，第一反应是“把所有柱子一起框进去，高度取最低的那个，宽度乘一下不就行了？”。结果被一个最朴素的例子打脸：柱子 [2,1,5,6,2,3]，整段框起来高度只有1，面积是6，可真正的答案是10。从那一刻起我就知道，这题值得写一篇完整的复盘。今天这篇每日一题，咱们不背模板，把单调栈的来龙去脉和几个隐蔽的大坑一次讲透。

1. 先想清楚题目在问什么：不是“最高的柱子”，而是“最宽的低谷”

1.1 矩形必须“贴地”，所以高度被最矮的那根柱卡死

题目的场景是这样的：n根柱子排成一排，每根宽度为1，高度给定。我们要找的矩形，底边落在柱状图底部，高度从底往上延伸，矩形的每一点下方都必须被柱子填实。换句话说，如果你选中了一个连续的柱子区间 [l, r]，这个矩形的高度只能是这个区间里柱子高度的最小值，宽度是 r - l + 1。

举一个最简单的例子，柱子高度是 [3, 1, 3]。整段区间 [0, 2] 的最小高度是 1，宽度是 3，面积是 3；但如果我们只看区间 [0, 0]，高度3、宽度1，面积3；区间 [2, 2] 同理面积3。所以答案是3。这个例子虽然简单，但它说明了一个关键事实：矩形面积并不总是越大区间越好，你要在“高度被最小柱子拖低”和“宽度够宽”之间做权衡。

1.2 经典用例 [2,1,5,6,2,3] 的答案为什么是 10

拿题目的经典样例来看，柱子高度依次为 2、1、5、6、2、3。肉眼观察，最高的柱子是高度6，但它左右很快就被5和2包围，能撑起的最大矩形是高度5、宽度2（由高度5和高度6两根柱子组成），面积 5×2=10。

如果你枚举所有连续区间，你会发现很多组合：

• 区间 [0,0]：高度2，宽1，面积2
• 区间 [0,1]：最小高度1，宽2，面积2
• 区间 [1,4]：最小高度1，宽4，面积4
• 区间 [2,3]：最小高度5，宽2，面积10
• 区间 [2,4]：最小高度2，宽3，面积6
• 区间 [4,5]：最小高度2，宽2，面积4

最大确实就是10。这个例子必须亲手过一遍，因为后面所有单调栈的推演都围绕它展开。

1.3 一个反直觉的结论：每根柱子都可能成为矩形的高

很多人以为最大矩形一定由“最高的柱子”决定，这是误解。在上面的例子里，高度6的柱子单独能撑出的最大面积是 6×1=6，而高度5的柱子联合旁边的高度6，反而撑出了10。所以正确的思考方式是：对每一根柱子，假设以它的高度作为矩形的高，看它左边和右边最多能延伸到哪里——只要遇到比自己矮的柱子，就停下来了。这样每个柱子都有一个“左右边界”，对应面积 = 自身高度 × 边界内柱子个数。取所有柱子的最大值，就是答案。

你要找的，是每根柱子左边第一个比它矮的柱子，以及右边第一个比它矮的柱子。这两个“最近的更矮位置”一旦确定，矩形宽度就确定了。

2. 暴力解法为什么不可行：不是不会写，是算不完

2.1 最朴素的枚举写法：O(n²) 看起来很合理

第一种暴力思路是枚举左端点 i 和右端点 j，维护区间最小高度。Python 写出来大概是这样：

def largestRectangleArea(heights): n = len(heights) max_area = 0 for i in range(n): min_h = float('inf') for j in range(i, n): min_h = min(min_h, heights[j]) max_area = max(max_area, min_h * (j - i + 1)) return max_area

这段代码非常直观，确实能跑出正确答案。第二种子思路是枚举“以哪根柱子作为矩形高度”，然后向左右两边扩展，直到碰到比它矮的柱子才停止。这个写法同样是 O(n²)，因为最坏情况下，比如柱子高度单调递增，每根柱子向左扩展都要扫过前面所有柱子。

2.2 O(n²) 在 LeetCode 上到底会发生什么

LeetCode 84 的 n 范围是 1 到 10^5。O(n²) 意味着最坏要做大约 10^10 次操作。现代 CPU 一秒钟大约能执行 10^8 到 10^9 次简单操作，所以 10^10 会让你的代码跑几十秒甚至几分钟。而平台的时限通常是 1 到 2 秒，暴力解法一定会被判定超时。

这其实暴露了一个很重要的刷题思维：提交之前先看数据规模。n 是 100，O(n²) 随便写；n 是 10^5，你就要警觉，必须设计 O(n²) 以下的算法。线性扫描、单调栈、双指针、二分，这些套路本质上都是为了把复杂度摁在 O(n log n) 或 O(n) 以内。

2.3 暴力解法真正的价值：用于对拍验证

暴力算法不是一无是处。我在本地做题时经常故意留一份暴力解法，用它和优化后的解法跑随机数据对拍。比如生成 1000 组随机高度数组，分别用暴力和单调栈计算结果，一旦不一致就能快速定位逻辑漏洞。这个习惯在面试前尤为重要，它能给你极大的信心，确保优化解法不是靠猜的。

3. 单调栈的核心原理：当柱子遇到第一个更矮的“右侧边界”

3.1 关键观察：一根柱子的右边界什么时候确定

从左往右遍历柱子。假设当前处理到下标 i，柱子高度 h = heights[i]。如果栈顶柱子的高度比 h 大，那么对于栈顶那根柱子来说，i 就是它“右边第一个比它矮的柱子”——因为更早在栈里的柱子都比它高，而现在终于出现了一个矮子，它作为矩形高度的右侧扩展到这里就必须停下来了。

那它的左边界是谁？答案是它在栈中的下一层元素。原因在于单调栈的构造规则：从栈底到栈顶，高度是严格递增的。所以当栈顶柱子 cur 即将被弹出时，新的栈顶 left 一定满足 heights[left] < heights[cur]，而且 left 是 cur 左边第一个比它矮的柱子。如果你觉得这句话有点绕，可以这样想：cur 被压入栈时，栈顶 left 是当时唯一比它矮的柱子，而之后压入栈的柱子都比 cur 高，它们不可能成为 cur 的“左边界”；所以 left 天然就是 cur 的左边第一个更矮柱子。

3.2 用 [2,1,5,6,2,3] 手动模拟一遍完整的入栈出栈

为了严谨，我给原数组前后各加一个高度为0的哨兵，得到 heights = [0, 2, 1, 5, 6, 2, 3, 0]，栈初始时放入左哨兵的下标0。后面表格就是逐步骤的推演。

最终结果是10，和暴力解法完全一致。你仔细看，每个柱子被弹出时，都恰好拿到了自己的最大展开宽度。柱子高度5之所以能拿到宽度2，是因为它弹出时左边最近更矮柱子是下标2（高度1），右边最近更矮柱子是下标5（高度2），于是区间就是下标3到4，宽度2。

3.3 为什么栈里存下标，而不是直接存高度

很多初学者会问：既然计算面积需要高度，为什么栈里不直接存高度值？答案是宽度必须由下标来计算。面积 = 高度 × 宽度，宽度是左右边界之间的柱子数量，边界都是下标位置，所以栈中必须存下标。高度需要时再通过 heights[cur] 取出来，反正数组就在那里，O(1) 访问。

另一方面，存下标还有一个微妙的好处：遇到高度相同的柱子时，下标能保留“谁先谁后”的次序信息，避免逻辑混乱。如果你直接存高度，宽度信息就完全丢失了，根本没法算。

3.4 每个元素只进出栈一次，所以复杂度是 O(n)

单调栈的入栈和出栈次数总共是 O(n)。每个下标最多入栈一次，最多出栈一次。虽然 while 循环里可能连续弹出多个元素，但累计次数不超过入栈次数。所以整体时间是 O(n)，空间是 O(n)。这是我能想到的对这道题最优雅的解法。

4. 哨兵柱子的设计：把边界问题从“写代码”变成“改数据”

4.1 朴素单调栈的尴尬：遍历结束后栈里还有剩

如果只在遇到“更矮柱子”时弹出，那么遍历完整个数组之后，栈里可能还残留一段递增的柱子没有计算。比如 [1,2,3,4,5]，从头到尾都不会触发弹出，最后栈是满的，最大面积会算成0，这显然是错的。你必须在循环结束后再写一段“清算”逻辑，把剩余元素挨个弹出，右边界统一设为 n。

清算代码本身不复杂，但初学者很容易漏，而且它和主循环里弹栈的逻辑高度重合，维护起来非常别扭。更麻烦的是，左边界为空的情况要额外判断，因为栈可能被弹空，此时左边界是 -1。

4.2 前后各放一个0：代码瞬间变得干净

经典做法是在 heights 数组的最前面和最后面各插入一个高度为0的哨兵柱子。左哨兵保证栈永远不会弹空，右哨兵保证所有真实柱子都会被弹出。一旦有了哨兵，主循环就可以统一逻辑，不需要任何“清算”段。

def largestRectangleArea(heights): h = [0] + heights + [0] stack = [0] # 左哨兵下标 max_area = 0 for i in range(1, len(h)): while h[i] < h[stack[-1]]: cur = stack.pop() left = stack[-1] width = i - left - 1 max_area = max(max_area, h[cur] * width) stack.append(i) return max_area

这段代码是很多题解的终极形态，短小精悍。注意，while 条件里用的是<，也就是说只在遇到严格更矮的柱子时才出栈；高度相等时不出栈。这个细节为什么可以这样，下一节单独讲。左哨兵0在栈底，永远不弹出（因为后面的柱子高度都大于等于0），所以 stack[-1] 一定安全，不会越界。

4.3 哨兵方案不是银弹：空间与数据完整性的权衡

哨兵方案有一个不算缺点的代价：复制了一份新数组，多用了 O(n) 空间。在力扣环境下这完全可接受。如果你在面试中写，可以主动向面试官说明这个空间开销，并且强调引入哨兵是为了简化边界判断、提高代码可读性。千万别在原数组上直接 append(0)，那会污染输入数据——万一后面还有别的逻辑要用原始 heights，就麻烦了。始终先复制，再处理。

5. 看题容易、写对很难：相等高度和边界坑的完整排查链路

5.1 高度相等时到底该不该弹出：<与<=的分野

这是最常见的争议点。比如 heights = [2, 2]，两根柱子一样高。如果出栈条件用<，流程是：第一根入栈，第二根因为 2 < 2 不成立，直接入栈；最终遇到末尾哨兵0时，两根柱子依次弹出，第一根弹出时宽度为2，得到面积 4。答案正确。

如果出栈条件用<=，流程是：第二根柱子来的时候，2 <= 2 成立，第一根立即弹出，此时宽度 i-left-1 = 2-0-1 = 1，面积2；随后第二根入栈，末尾弹出时宽度也是2，面积4。答案还是正确。

所以两种写法都能通过。区别在于计算时机不同，但结果一致。我个人的建议是统一写成<，因为它更贴合“遇到第一个比自己矮的柱子才算右边界”的语义；用<=虽然在不少题解里也能跑，但容易让你误以为“相等也算更矮”，以后遇到更复杂的变体题时容易想岔。

5.2 宽度公式为什么是 i - stack[-1] - 1，而不是 i - cur

这是另一个高频翻车点。很多人观察到当前柱子下标是 i，弹出的下标是 cur，就觉得宽度应该是 i - cur + 1 或者 i - cur。问题出在：当 cur 弹出后，新的栈顶 left 不一定等于 cur - 1，因为中间可能夹着别的柱子。

举个例子，在 [2,1,5,6,2,3] 的模拟中，弹出下标3（高度5）时，cur=3，i=5，而新的栈顶 left=2。如果按 i - cur = 2，宽度是2，但实际矩形覆盖的是下标3和4，宽度确实是2，看起来碰巧一样。但换一个场景，弹出下标5（高度2）时，cur=5，i=7，left=2，此时 i - cur = 2，实际宽度却是区间下标3到6，也就是4。按公式 i - left - 1 = 7 - 2 - 1 = 4，就对了。

所以宽度的准确含义是：右边界 i（当前柱子）和左边界 left（弹出后的新栈顶）之间的开区间长度。开区间 (left, i) 包含的柱子总数就是 i - left - 1。任何拿 cur 直接参与宽度计算的写法，都是在碰运气。

5.3 忘记末尾哨兵：在单调递增数组上必然翻车

假设 heights = [1,2,3,4,5]，如果你只加了左哨兵没加右哨兵，遍历结束后栈里是 [0,1,2,3,4,5]，所有元素都没被弹出，最大面积计算结果为0。遇到这种单调递增的用例，任何没写“清算段”的朴素单调栈都会错。

如果你坚决不用右哨兵，那循环结束后必须补一段：

while len(stack) > 1: cur = stack.pop() left = stack[-1] width = len(heights) - left - 1 max_area = max(max_area, heights[cur] * width)

这段代码本身没问题，但你已经多写了一层逻辑。每多一层分支，就多一分出错的可能。这就是我为什么强烈推荐双哨兵方案——它把“清算”合并进了主循环，让代码只有一条路径。

5.4 复制数组时的常见低级错误

写h = heights[:]然后h.append(0)和h.insert(0, 0)，顺序稍微一乱，下标很容易对不上。我建议用最稳妥的拼接写法：

h = [0] + heights + [0]

一步到位，复制和哨兵一起完成。栈初始化为[0]，对于后续遍历，for 循环从下标 1 开始，直接跳过左哨兵。这里再强调一次：栈里放的是 h 的下标，不是原数组 heights 的下标，所以后面取高度都用h[cur]，千万别混用 heights 和 h。

5.5 空数组和单元素数组的边界

如果 heights = []，加了哨兵后 h = [0, 0]，栈初始 [0]，遍历 i=1 时 0 < 0 不成立，直接入栈，最终面积为0，没问题。如果 heights = [3]，h = [0,3,0]，模拟一下：i=1 入栈；i=2 时 0<3，弹出 cur=1，left=0，width=2-0-1=1，面积3。完全正确。所以双哨兵方案对最小输入也是稳健的。

6. 从 84 到 85：一个套路吃透“最大矩形”家族

6.1 和“接雨水”互为镜像：一个找洼地，一个找高地

LeetCode 42“接雨水”和这道题是天生一对。接雨水的目标是找每个凹槽能存多少水，它关心的是“左边和右边第一个比自己高的柱子”，因为水的高度被较矮的墙限制，所以典解法是单调递减栈。而柱状图最大矩形关心的是“左边和右边第一个比自己矮的柱子”，因为矩形的高度被最高的可用柱子限制，用单调递增栈。

这两个题放到一起学特别有味道：一个在找“坑”，一个在找“峰”；一个弹出时计算的是积水面积，一个弹出时计算的是矩形面积。代码结构高度相似，都是边遍历边维护栈，但出栈判断条件完全相反。你要是能把这两题背靠背吃透，单调栈基本就过关了。

6.2 LeetCode 85“最大矩形”：把二维矩阵逐行转成一维

二维的“最大矩形”题（LeetCode 85）给的是一个 0/1 矩阵，要求找出只包含 1 的最大矩形面积。标准解法是：从上到下遍历每一行，维护一个高度数组 heights[j]。如果当前行 matrix[i][j] == '1'，heights[j] 就加1；否则 heights[j] 直接清零。这样每一行都得到一个直方图，把这个直方图丢给 84 题的解法，得到当前行作为底边的最大矩形面积。对每一行都执行一次，全局最大值就是答案。

def maximalRectangle(matrix): if not matrix or not matrix[0]: return 0 n = len(matrix[0]) heights = [0] * n max_area = 0 for row in matrix: for j in range(n): if row[j] == '1': heights[j] += 1 else: heights[j] = 0 max_area = max(max_area, largestRectangleArea(heights)) return max_area

时间复杂度是 O(m·n)，每一行调用一次84题的线性算法。如果没有掌握84题，这题会难出天际；掌握了之后，它就是一个循环套一个子函数的事。

6.3 这类“找最近更小元素”的套路，在真实场景里的影子

单调栈不只是刷题用的。在直方图统计、图像二值化后的最大空白矩形检测、柱状分布图中寻找最佳阈值范围等场景里，你都会看到“找最近更矮/更高柱子”这类需求。比如在图像处理中，把每一行像素看作柱子高度，最大矩形面积可以用来定位印刷版面里的最大空白区域。这类问题本质上都在问：给定一组高低不平的数据，如何高效找到某个方向上“受最近极值约束的最优区间”。理解了84题，你等于掌握了一把处理这类区间约束问题的通用钥匙。

从这道题里带走的三个实际操作建议

最后说点我个人的刷题体会。第一，碰到这种经典题，不要直接抄模板，先自己写出暴力解法，再手动模拟一遍单调栈的进出过程。我在纸上模拟 [2,1,5,6,2,3] 不下五遍之后，才真正理解“为什么弹出时能计算出最大面积”这个瞬间。第二，代码写完后，一定要跑几个特殊用例：单调递增数组、单调递减数组、全部相等高度、单元素、空数组。这些用例能把索引和边界问题全部暴露出来。第三，优先采用双哨兵写法，它让主循环干净到一眼能看穿，以后面试手写时也少一份紧张。

如果你今天刚好在做每日一题，建议把 84 和 42 安排在同一天，再用 85 作为第二天的巩固题。真正把这道题吃透之后，你再看其他栈相关的题目，会觉得底气和之前完全不同。