题目重点：用非递减下标栈找左右较矮边界，讲清重复高度、末尾清栈和线性摊销。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 柱宽均为1，高度非负整数，空数组面积0；矩形必须连续覆盖若干完整柱。
- 代码保留相等高度，只有严格更低的新柱才弹栈。
- 函数返回面积，输入不改；如柱宽不等，需要前缀宽度替代下标差。
解题路线
- 任意候选矩形的高度可取覆盖柱的最小高度。目标是在每个可能限制高度上找到能延伸的最大连续宽度，暴力枚举区间O(n²)，单调栈把边界统一求出。
- 栈存高度非递减的柱下标。当前height更低时，栈顶柱无法继续延伸到i，因此弹出它并计算以该height为限制的面积。
- 弹出后若栈非空，其栈顶left是此轮可用的左界；有效列为left+1..i−1，共i−left−1。栈空表示能延伸到0，left=−1，宽度i。
- 相等高度留在栈里时，早先等高柱稍后会被弹出并得到更大宽度；不要求每次弹栈都必须是严格更低的左边界，最终至少一个同高度候选覆盖整个可行区间。
- 最后模拟一根0柱触发剩余正高度清栈，不把哨兵作为真实输入修改。0高度自身留栈不影响最大面积，面积为0。
- 每个下标入栈一次出栈至多一次，while虽然嵌套for，总操作O(n)。没有必要把最坏单次弹n个错误乘成n²，也不能因均摊线性就称每一步实时常量。
- 若返回最优区间，计算时保存left+1/i−1/height并定义tie-break。非等宽、动态更新或二维最大矩形都改变合同，后者可逐行累计高度再调用该子问题。
手动走一遍
[2,1,5,6,2,3]处理下标4高度2时，先弹6宽1面积6，再弹5，左界为1、右界为4，宽4−1−1=2，面积10。[2,2]末尾0会依次弹出，最左2获得宽2面积4。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Unit-width bars, nonnegative integer heights, empty histogram area zero."""
def largest_rectangle(heights):
if any(not isinstance(v, int) or isinstance(v, bool) or v < 0 for v in heights):
raise ValueError('nonnegative integer heights required')
stack = []
answer = 0
for i in range(len(heights) + 1):
current = heights[i] if i < len(heights) else 0
while stack and heights[stack[-1]] > current:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
answer = max(answer, height * (i - left - 1))
stack.append(i)
return answer
复杂度
O(n)时间、O(n)栈空间，输出一个面积O(1)。面积计算用足够宽整数，柱宽乘高度可能超过32位。
易错点与追问
容易失分的边界
- 宽度忘减1。
- 只弹一次而不是直到恢复单调。
- 未清空末尾递增柱。
- 改等宽合同后仍用下标差当宽度。
继续深挖
- 怎样返回矩形左右下标？
- 所有高度相等时哪个候选得到全宽？
- 二维0/1矩阵如何复用？
- 动态更新高度为何不再是一次线性扫描？
