LeetCode 84困难单调栈
柱状图中最大的矩形 图解题解
柱状图里能圈出的最大矩形，暴力枚举超时——单调栈让每根柱子在弹出时精确算出以自身为高的最大宽度，O(n) 找到答案。
从左往右扫柱子，栈里存已扫过的柱子下标，从底到顶高度递增。新柱子比栈顶矮时，栈顶那根柱子就找到了它的「右边界」（当前柱子），弹出结算：高度 = 弹出柱子的高度；宽度 = 当前下标 i 减去弹出后新栈顶的下标再减 1（左右两侧第一个比它矮的柱子之间的距离）。反复弹到栈顶不比新柱子高为止，再把新柱子下标压栈。扫完后栈里剩的柱子右边再也没有比它矮的，用末尾哨兵（高度 0）强制触发最后一轮结算。
这道题到底在问什么
给柱状图高度，求能组成的最大矩形面积。
- heights
- [2,1,5,6,2,3]
- 输出
- 10
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合单调栈。
- 4单调栈：维护一个高度递增的下标栈。思路：以每根柱的高作矩形高，宽向左右扩到第一个更矮的柱。i=0，栈空 → 压入柱 0。
- 5i=1 高度 1 ＜ 栈顶柱 0(高2) → 弹出柱 0 结算：高 2 × 宽 1 = 2。再压入柱 1。栈=[1]。
- 6柱 2(5)、柱 3(6) 都比栈顶高 → 直接压栈。栈=[1,2,3]，高度 1,5,6 递增。
- 7i=4 高度 2 ＜ 6 → 弹柱 3：高6×宽1=6；仍 ＜ 5 → 弹柱 2：高 5 × 宽 2 = 10(柱 2、3 这段，蓝框)。这就是最大矩形！宽 = 当前 i 到栈中前一个的距离。
- 8结算完把柱 4(2)、柱 5(3) 压栈，继续扫描。栈=[1,4,5]。
- 9扫到末尾后补一个哨兵 0，把栈里剩的柱全弹出结算(不会漏)。全程最大矩形面积 = 10。
- 12把这句话记住，下次遇到同类题，就能更快选出方向。
- 17把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：只看相邻两根柱子
✓ 对：弹栈时用左右第一个更矮确定宽度
最大矩形可能跨很多柱子
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def largestRectangleArea(self, heights):
heights.append(0)
stack = []
ans = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
mid = stack.pop()
left = stack[-1] if stack else -1
ans = max(ans, heights[mid] * (i - left - 1))
stack.append(i)
heights.pop()
return ansC++
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
stack<int> st;
int ans = 0;
for (int i = 0; i < (int)heights.size(); i++) {
while (!st.empty() && heights[st.top()] > heights[i]) {
int mid = st.top(); st.pop();
int left = st.empty() ? -1 : st.top();
ans = max(ans, heights[mid] * (i - left - 1));
}
st.push(i);
}
return ans;
}
};Java
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
Deque<Integer> st = new ArrayDeque<>();
int ans = 0;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!st.isEmpty() && heights[st.peek()] > h) {
int mid = st.pop();
int left = st.isEmpty() ? -1 : st.peek();
ans = Math.max(ans, heights[mid] * (i - left - 1));
}
st.push(i);
}
return ans;
}
}套路模板 · 单调栈
# 单调栈 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
stack<int> st;
int ans = 0;
for (int i = 0; i < (int)heights.size(); i++) {
while (!st.empty() && heights[st.top()] > heights[i]) {
int mid = st.top(); st.pop();
int left = st.empty() ? -1 : st.top();
ans = max(ans, heights[mid] * (i - left - 1));
}
st.push(i);
}
return ans;
}
};class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
Deque<Integer> st = new ArrayDeque<>();
int ans = 0;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!st.isEmpty() && heights[st.peek()] > h) {
int mid = st.pop();
int left = st.isEmpty() ? -1 : st.peek();
ans = Math.max(ans, heights[mid] * (i - left - 1));
}
st.push(i);
}
return ans;
}
}复杂度
时间复杂度
O(n)
每个核心状态按算法要求处理固定次数
空间复杂度
O(n)
只保存必要的辅助结构或递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 柱状图中最大的矩形 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
单调栈怎么求每根的左右边界？+
递增栈：弹出栈顶时，当前柱是它的右边界、栈里下一个是它的左边界，宽度一步算出。
为什么是 O(n)？+
每根柱最多入栈、出栈各一次。
和「接雨水」的单调栈区别？+
接雨水栈递减、算凹槽蓄水；本题栈递增、算被弹柱能撑起的最大矩形。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。