算法面试：如何求柱状图中的最大矩形？

题目与适用场景

给定数组 heights，每个数表示一根宽度为 1 的柱子。合法矩形需要覆盖一根或多根连续柱子， 底边落在基线上，高度不能超过覆盖区间内最矮的柱子。返回最大的矩形面积。

heights = [2, 1, 5, 6, 2, 3]
answer = 10

最优矩形覆盖下标 2..3：高度为 5，宽度为 2，面积为 10。标准约束是 1 <= heights.length <= 100000、0 <= heights[i] <= 10000。本文额外约定空数组返回 0。 在标准约束下，面积最多为 10^9，JavaScript 的 number 可以精确表示。

当前英文面试准备资料与一份独立的中文公开题解都把这道原题作为单调栈练习；原始题面和当前 DSA 指南也采用相同的单位宽度模型与约束。因此可将其视为有代表性的 coding 题，无须归属 某家公司，也不声称无法核验的出现频率。

面试官在考察什么

第一，看你能否在不枚举所有左右边界的前提下覆盖全部候选矩形。选定一个高度后，它的最宽矩形 会一直延伸到左右第一个严格更矮的柱子。几何问题因此转化为“寻找最近更小元素”。

第二，看你能否从这个关系推导数据结构。递增栈保留右边界尚未确定的柱子。更矮柱出现时，会一次 关闭一根或多根柱子的候选矩形：当前下标是它们右侧第一个更矮位置，栈中保存的起点已经编码了 它们能向左延伸到哪里。

第三，看你是否能正确处理相等高度与数组边界。相等高度不应留下起点不同、互相竞争的栈项；扫描 结束时还在栈里的柱子也必须获得右边界。可靠实现会明确这两个规则，而不是只背宽度公式。

最后，嵌套的 while 需要摊还分析。一次循环可能弹出多个栈项，但每个栈项只会入栈一次、出栈 一次，所有栈操作的总数仍是线性的。

回答前要澄清的问题

• 每根柱子的宽度都是 1 吗？ 是。宽度可变时，左边界状态和面积公式都要调整。
• 矩形必须覆盖连续柱子吗？ 是。中间的矮柱不能被跳过。
• 高度可以为零或重复吗？ 可以。零会隔断正面积矩形；相等高度需要统一的入栈规则。
• 数组可能为空吗？ 标准题面排除了空数组，本文实现将返回 0 作为明确扩展。
• 只返回面积吗？ 是。若要返回坐标，还需保留获胜矩形的起点、终点、高度并定义并列规则。
• 可以修改输入吗？ 不需要；本文使用虚拟哨兵，不会向原数组追加元素。
• 面积会溢出吗？ 给定约束下不会。生产接口若扩大范围，应先计算上界，再按需要使用 bigint 或更宽整数。
• 必须达到线性时间吗？ 是。O(n^2) 基线适合推导和测试，但无法满足目标规模。

30 秒回答框架

“对高度为 h 的柱子，它的最宽合法矩形会在左右第一个更矮柱之前停止。我从左到右扫描，用 严格递增高度的 (start, height) 栈。当前高度低于栈顶时，当前下标就是栈顶右侧第一个更矮 边界，于是弹栈并计算 height * (right - start)。我把弹出的 start 向左传递，因为当前更矮 柱能跨过刚刚移除的所有高柱。高度相等时保留更早的栈项。最后扫描一根虚拟的零高柱，关闭剩余 矩形。每个栈项最多入栈、出栈一次，因此时间为 O(n)，辅助空间为 O(n)。”

逐步深入解法

步骤一：建立正确基线。

对每个区间 [left, right]，维护其中的最小高度。覆盖整个区间的最大矩形面积是：

min(heights[left..right]) * (right - left + 1)

固定 left 后向右扩展并更新最小值，可得到 O(n^2) 时间、O(1) 空间的基准算法。它无法 处理 n = 100000 的最坏输入，却很适合在小规模随机数组上校验优化解法。

步骤二：反转枚举方式。

不再为每个区间寻找最矮柱，而是选定一根柱子作为矩形的限制高度。若左右最近的严格更矮位置是 leftShorter 和 rightShorter，该柱可覆盖：

(leftShorter + 1) .. (rightShorter - 1)
width = rightShorter - leftShorter - 1

这是以该柱高为限制时的最宽矩形。对所有限制高度取最大值，就是全局答案。

步骤三：让递增栈保存尚未闭合的柱子。

栈中保存 { start, height }，高度严格递增。start 是在此前所有已关闭高柱被移除后，该高度 仍然有效的最早下标。新高柱从自身下标开始；新矮柱会关闭更高栈项，并继承最早的弹出起点。

以 [2, 1, 5, 6, 2, 3] 为例，下标 4 的高度 2 先弹出 6，得到 6 * 1；再弹出 5，得到 5 * 2 = 10。它继承起点 2，因为高度 2 可以跨过刚才两根高柱。栈中的高度 1 更矮，阻止它继续向左延伸。

步骤四：定义相等高度和收尾规则。

当前高度与栈顶相等时，保留较早栈项。两者高度相同，但早期栈项起点更靠左，能得到的最优矩形 不会更窄。在下标 n 处扫描一根虚拟的高度 0 柱，可关闭所有正高度栈项，无须修改输入，也 无须重复一套清栈面积逻辑。

步骤五：实现不变量并证明弹栈计算。

interface StackBar {
  start: number
  height: number
}

export function largestRectangleArea(heights: number[]): number {
  const stack: StackBar[] = []
  let maxArea = 0

  for (let right = 0; right <= heights.length; right += 1) {
    const height = right === heights.length ? 0 : heights[right]
    let start = right

    while (stack.length > 0 && stack[stack.length - 1].height > height) {
      const bar = stack.pop()!
      maxArea = Math.max(maxArea, bar.height * (right - bar.start))
      start = bar.start
    }

    const top = stack[stack.length - 1]
    if (height > 0 && (!top || top.height < height)) {
      stack.push({ start, height })
    }
  }

  return maxArea
}

每轮扫描前保持三个不变量：

1. 栈内高度严格递增。
2. 对每个栈项，从 start 到 right - 1 的所有已处理柱高都不低于它。
3. 这段范围内不存在已处理的严格更矮柱；否则该栈项早已被弹出。

更矮高度出现时，不变量 2 和 3 说明被弹栈项可以延伸到 right - 1；当前柱又证明它不能覆盖 right。因此它的最大宽度恰好是 right - start，此时计算的面积已经完整。把弹出起点交给 当前高度是安全的，因为当前高度低于所有刚移除的柱子。跳过相等高度也是安全的，因为被保留的 同高栈项起点不会更晚。哨兵会关闭所有右侧没有真实矮柱的栈项。于是每一种可能的限制高度都计算 了自己的最大矩形，maxArea 就是全局最优值。

步骤六：验证边界输入与复杂度。

固定用例应分别攻击不同不变量：

更强的可执行验证是：在大量小随机数组上，把单调栈结果与平方级基准算法逐一比较。本文实现已经 通过 7 个固定用例，以及 20000 个长度为 0..8、高度为 0..7 的随机数组。可执行校验不能 替代证明；上面的不变量负责覆盖所有可能输入。

每个正高度最多入栈一次、出栈一次，所以总时间为 O(n)。严格递增输入会让全部 n 个栈项 保留到哨兵处，因此最坏辅助空间为 O(n)。

高质量示范回答

“我会先建立平方级基准：固定每个左边界，向右扩展并维护最小高度。它覆盖了所有区间，但无法 处理 10 万根柱子的目标规模。重复出现的问题是：选定一个高度后，它在遇到更矮柱之前能延伸 多远。这正是最近更小边界，可以用单调栈解决。

我的栈保存每个尚未闭合高度的最早有效起点，并保持高度严格递增。扫描到下标 right 时，只要 栈顶高于当前柱就弹栈。当前下标是被弹柱子的第一个无效位置，所以它的最大面积是 bar.height * (right - bar.start)。我把它的起点传给当前高度，因为这根更矮柱可以覆盖刚移除 的所有高柱。当前高度与栈顶相等时保留更早项，不再重复入栈。最后用一根虚拟零高柱关闭剩余 后缀。

栈不变量保证每个栈项从起点到当前位置之前的柱子都足够高，当前更矮柱则让它的右边界最终确定。 每个栈项最多入栈、出栈一次，所以时间为 O(n)，最坏空间为 O(n)。我会测试相等高度、递增与 递减数组、零高度、扩展约定下的空输入，并用平方级基准比对随机小数组。”

常见错误

每个错误都有具体原因和修正方式：

• 弹栈后使用 right - start + 1 → right 已是第一个无效位置 → 应使用 right - start。
• 忘记最终清栈 → 递增后缀从未计算 → 多扫描一根虚拟零高柱。
• 每个相等高度都入栈 → 正确性依赖更微妙的弹栈规则 → 保留最早的同高栈项。
• 认为内层循环导致平方时间 → 每个栈项只能弹出一次 → 给出摊还次数。
• 把哨兵追加到 heights → 调用方观察到输入被修改 → 虚拟计算哨兵。

追问深入

追问一：如何返回矩形边界？

每当面积变大时，同时保存 { start: bar.start, end: right - 1, height: bar.height }。编码前要 先定义并列规则：优先最靠左、最宽，还是最高的矩形。面积相同并不能唯一确定答案。

追问二：柱子宽度可变怎么办？

用物理宽度的前缀和替代下标差。栈项需要保存最早水平坐标，弹栈面积变为 height * (currentX - startX)。零宽柱和非法负宽度都需要明确接口约定。

追问三：如何扩展到二进制矩阵？

把每一行当作柱状图底边。当前格为 1 时累加该列高度，为 0 时清零；每处理一行就运行一次 柱状图算法。对 m × n 矩阵，时间为 O(mn)，辅助空间为 O(n)。

追问四：数据以流形式到达时能否维护精确答案？

栈可以在线接收柱子，但流右端仍开放的矩形尚未最终确定。需要快照时，可以用当前长度计算这些 栈项的临时面积而不弹栈。严格递增流会让精确状态增长到 O(n)；从这个不变量无法得到固定内存 的精确算法。

追问五：输入大到单机内存放不下怎么办？

只计算每个分块内部最大值不够，因为获胜矩形可能跨越分块边界。分布式摘要必须保留足够的边界 高度结构才能合并相邻块，而单调分块的边界结构本身可能是线性的。承诺常量大小摘要前，应先说明 这个下界风险。

追问六：什么时候更适合其他方案？

平方级基准最适合小输入校验。围绕最小值做分治有助于推导递推关系，但每层线性寻找最小值会在 有序输入上退化到 O(n^2)。区间最小值数据结构适合还要处理其他重复查询的场景；只求一次静态 最大面积时，单调栈更简单，并达到渐近最优。