84. 柱状图中最大的矩形 (Hard)
专题归类： 06-栈与堆 · 03-数组与矩阵 LeetCode 链接： https://leetcode.cn/problems/largest-rectangle-in-histogram/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1：
输入：heights = [2,1,5,6,2,3]
输出：10
（最大矩形面积为 10，由高度为 2、宽度为 5 的矩形构成，或高度为 5、宽度为 2 的矩形构成）
示例 2：
输入：heights = [2,4]
输出：4
题目详细分析
- 数据范围： 1 ≤ heights.length ≤ 10^5，0 ≤ heights[i] ≤ 10^4。数组长达 10 万，O(n²) 会超时。
- 输入输出特征： 非负整数数组，可能有高度为 0 的柱子（即空隙）。每个柱子宽度固定为 1。
- 边界条件：
- 高度为 0 的柱子：不能作为矩形的一部分，它会把左右两边的柱子隔开。
- 所有柱子高度相同：最大矩形 = 高度 × 柱子数。
- 高度递增/递减序列：需要特殊处理，通常用哨兵简化。
- 核心约束： 必须找到全局最大矩形，矩形必须连续覆盖若干完整柱子（不能只覆盖柱子的一部分宽度）。
- 隐藏条件：
- 对于每个柱子 i，以 heights[i] 为高的最大矩形 = heights[i] × (右边第一个更矮柱子的索引 - 左边第一个更矮柱子的索引 - 1)。
- 单调栈是解决此类问题的最优方案——可以在一次遍历中找到每个柱子的左右边界。
- 与 739「每日温度」找下一个更大元素不同，本题需要同时找左右两边第一个更小的元素。
小白版直白理解
就像一排高度不同的积木，你想找一个最大的长方形区域，这个区域的底边完全落在积木的顶部或地面。
关键洞察：对每个积木来说，它能贡献的最大矩形面积就是它自己的高度乘以它能向左右延伸的最远宽度。但能延伸多远呢？延伸到遇到比自己矮的积木为止（因为矮积木会挡住长方形）。
所以我们需要为每个柱子找到：
- 左边第一个比它矮的柱子（左边界）
- 右边第一个比它矮的柱子（右边界）
然后面积 = 高度 × (右边界 - 左边界 - 1)，取最大值。
单调栈就是用来高效找到这些边界的工具。想象你有一排人按身高站好，你从左边开始看，用栈记录那些暂时还没找到右边更矮的人的柱子。
解题思路
思路一：单调递增栈 + 哨兵（推荐）
核心思想： 维护一个单调递增栈（栈底到栈顶递增）。遍历高度数组，如果当前高度 < 栈顶高度，说明栈顶柱子找到了右边第一个更矮的柱子，可以弹栈计算面积了。
为什么用单调递增栈？因为我们要找的是「更矮」的柱子作为边界，而递增栈保证了栈中每个元素的下一个更矮元素就是当前要入栈的元素（如果它更矮的话）。
def largestRectangleArea(heights):
# 前后加 0 作为哨兵，简化边界处理
heights = [0] + heights + [0]
stack = [] # 单调递增栈，存索引
max_area = 0
for i in range(len(heights)):
# 当前高度小于栈顶高度 → 可以计算以栈顶高度为高的矩形面积了
while stack and heights[stack[-1]] > heights[i]:
h = heights[stack.pop()] # 以弹出柱子的高度为高
w = i - stack[-1] - 1 # 宽度 = 右边界 - 左边界 - 1
max_area = max(max_area, h * w)
stack.append(i)
return max_area复杂度： 时间 O(n)，空间 O(n)
为什么加哨兵 0？
- 左边加 0：保证栈不会为空（0 始终在栈底），避免计算宽度时
stack[-1]不存在。 - 右边加 0：保证最后栈中所有柱子都能被弹出计算（0 比所有正数都小）。
思路二：暴力法（中心扩散）
对每个柱子，向左找到第一个比它矮的，向右找到第一个比它矮的，计算面积。
def largestRectangleArea(heights):
n = len(heights)
max_area = 0
for i in range(n):
h = heights[i]
# 向左扩展
left = i
while left > 0 and heights[left - 1] >= h:
left -= 1
# 向右扩展
right = i
while right < n - 1 and heights[right + 1] >= h:
right += 1
max_area = max(max_area, h * (right - left + 1))
return max_area复杂度： 时间 O(n²)，空间 O(1)。对于 10^5 的数据规模会超时。
思路三：两次遍历求左右边界
一次从左到右遍历找到每个柱子左边第一个更矮的索引；一次从右到左遍历找到每个柱子右边第一个更矮的索引。最后统一计算面积。
def largestRectangleArea(heights):
n = len(heights)
left = [-1] * n # 左边第一个更矮的索引（没有则为 -1）
right = [n] * n # 右边第一个更矮的索引（没有则为 n）
# 求左边界
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
left[i] = stack[-1] if stack else -1
stack.append(i)
# 求右边界
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
right[i] = stack[-1] if stack else n
stack.append(i)
# 计算最大面积
max_area = 0
for i in range(n):
w = right[i] - left[i] - 1
max_area = max(max_area, heights[i] * w)
return max_area复杂度： 时间 O(n)，空间 O(n)
易错点
- 哨兵 0 的作用： 不加哨兵时，需要在 while 循环中检查栈是否为空；计算宽度时
stack[-1]可能不存在。左右哨兵 0 避免了这些特殊情况。 - 宽度计算公式：
w = i - stack[-1] - 1。其中stack[-1]是弹出后新的栈顶（即左边第一个更矮柱子的索引），i是右边第一个更矮柱子的索引。两者之间的柱子数（不包括它们自己）就是宽度。 - while 条件是
>还是>=： 使用>=或>会影响计算结果。因为相同高度的柱子，用>会保留左边的相同高度柱子作为边界，计算出的面积更准确。实际上用>=也可以，但需要保证一致性。 - int 范围： heights[i] 最大 10^4，长度最大 10^5，面积最大可达 10^9，在 32 位 int 范围内，但 Python 不存在溢出问题。
- 柱子高为 0： 高度为 0 的柱子无法贡献面积，但它会起到边界作用，分割左右两边的计算。
框架提炼
单调栈求「下一个更小元素」模板：
def next_smaller_left(nums):
"""返回每个元素左边第一个比它小的元素的索引（没有则返回 -1）"""
n = len(nums)
res = [-1] * n
stack = []
for i in range(n):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
res[i] = stack[-1] if stack else -1
stack.append(i)
return res
def next_smaller_right(nums):
"""返回每个元素右边第一个比它小的元素的索引（没有则返回 len(nums)）"""
n = len(nums)
res = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
res[i] = stack[-1] if stack else n
stack.append(i)
return res单调栈应用场景汇总：
- 下一个更大元素（739. 每日温度）
- 最大矩形面积（84. 柱状图中最大的矩形）
- 接雨水（42. 接雨水）
- 最大宽度的坡（962. 最大宽度坡）