柱状图中最大的矩形
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定 n 个非负整数，表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1
示例 2
模拟答题者思考
1. 暴力：枚举每一根柱子作为矩形「最短边」，向左右扩展到第一个更矮的柱子——正确，但单柱 O(n)，总体 O(n²)。
2. 重复劳动：对每根柱子「向左/向右第一个更矮」是同类区间问题；若已知每柱左右边界，面积 = 高 × (右边界 - 左边界 - 1)。
3. 单调栈：从左到右扫，栈里保持高度递增的下标。遇到 heights[i] 比栈顶矮，说明栈顶柱子的「右边界」就是 i，弹出并结算；左边界是弹出后新栈顶（或 -1）。
4. 与接雨水对比：接雨水在「变高」时弹出算凹槽；本题在「变矮」时弹出，以被弹出柱为矩形高度向左右撑满。
5. 收尾：末尾可在 heights 后补一个高度 0 的哨兵，或第二轮把栈里剩余下标全部弹出（右边界视为 n）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
st | stack<int> | 定义：存下标，栈内对应高度单调递增（栈底到栈顶高度非降） 维护：尚未被「右侧更矮柱子」截断的柱子下标 更新：当前高度 ≥ 栈顶高度时压入 i；否则弹出栈顶并结算以该柱为最短边的矩形 |
mid | int | 定义：被弹出的柱子下标，矩形高度取 heights[mid]维护：每次 heights[i] < heights[st.top()] 时由 st.pop() 得到更新：结算一次最大候选面积后可能继续弹出 |
left | int | 定义：矩形左边界的前一个下标（开区间左端） 维护： mid 弹出后若栈非空则为 st[-1]，否则为 -1更新：宽度 w = i - left - 1（左右均为「第一个更矮」的位置） |
ans | int | 定义：遍历过程中见过的最大矩形面积 维护：每次弹出 mid 时用 heights[mid] * w 取 max更新： ans = max(ans, heights[mid] * (i - left - 1)) |
落码步骤
1. 初始化空栈 st，ans = 0；可选 heights.append(0) 作哨兵
2. 遍历下标 i，当栈非空且 heights[i] < heights[st[-1]] 时循环
3. mid = st.pop()，left = st[-1] if st else -1，w = i - left - 1
4. ans = max(ans, heights[mid] * w)
5. 循环结束后 st.append(i)；全部扫完后若未用哨兵，再对栈中剩余下标重复 3~4（右边界为 n）
代码实现
class Solution:
def largestRectangleArea(self, heights: list[int]) -> int:
st = [] # 单调递增栈，存下标
ans = 0
heights = heights + [0] # 哨兵：保证栈内柱子最终被结算
for i, h in enumerate(heights):
while st and h < heights[st[-1]]:
mid = st.pop()
left = st[-1] if st else -1
w = i - left - 1
ans = max(ans, heights[mid] * w)
st.append(i)
return ansclass Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st; // 单调递增栈，存下标
int ans = 0;
heights.push_back(0); // 哨兵
for (int i = 0; i < heights.size(); i++) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int mid = st.top(); st.pop();
int left = st.empty() ? -1 : st.top();
int w = i - left - 1;
ans = max(ans, heights[mid] * w);
}
st.push(i);
}
return ans;
}
};
// 时间 O(n)，空间 O(n)复杂度分析
O(n)
O(n)
常见坑
宽度公式：左边界是「前一个更矮」的下标 left，宽度为 i - left - 1，不是 i - mid（除非左右都扩展到 mid）。
单调方向与接雨水相反：本题栈内递增，在「当前更矮」时弹出；接雨水常是递减栈在「当前更高」时弹出。
忘记收尾：不用哨兵时，遍历结束后栈内下标仍需以右边界 n 结算，否则会漏掉以末尾柱子为最短边的矩形。
必测边界 Case
heights = [5] → 5
heights = [1,2,3,4] → 6（取中间 2×3 或 3×2 等，最大为 6）
heights = [2,2,2] → 6（整段宽度 3）
heights = [0,2] → 2（0 会把矩形截断）