84. 柱状图中最大的矩形
一句话套路单调递增栈 + 首尾 0 哨兵结算宽度
题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:

输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
示例 2:

输入: heights = [2,4] 输出: 4
提示:
1 <= heights.length <=1050 <= heights[i] <= 104
思路
时间
O(n)空间
O(n)思路
枚举「以某根柱子的高度为准」能撑多宽 —— 即左右第一个更矮的柱子在哪。
单调递增栈一次遍历搞定
当 h[i] 小于栈顶时弹出 t,弹出后新栈顶 left 就是 t 左边第一个更矮的位置,i 是右边第一个更矮的位置,于是宽度 = i - left - 1。
首尾各加一根 0 哨兵,免掉「栈空」和「收尾未结算」两种特判。
联动
Q85 最大矩形 = 把每一行当作柱状图的底,逐行调用本函数。
数值范围
高度 <= 10^4、n <= 10^5,面积最大 10^9,int 刚好装得下(2^31-1 ≈ 2.1×10^9);
范围再大一档(比如高度 10^5)就必须换 long long 了。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0084 {
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> h;
h.reserve(heights.size() + 2);
h.push_back(0); // 左哨兵:保证栈里永远有一个更矮的柱子
for (int x : heights) h.push_back(x);
h.push_back(0); // 右哨兵:保证结束时全部结算完
stack<int> st; // 单调递增栈(存下标)
int best = 0;
for (int i = 0; i < (int)h.size(); ++i) {
while (!st.empty() && h[i] < h[st.top()]) {
int height = h[st.top()];
st.pop();
int left = st.top(); // 左边第一个更矮的
best = max(best, height * (i - left - 1));
}
st.push(i);
}
return best;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0084::Solution s;
vector<int> a{2, 1, 5, 6, 2, 3};
CHECK_EQ(s.largestRectangleArea(a), 10); // 高 5、宽 2(柱子 5 和 6)
vector<int> b{2, 4};
CHECK_EQ(s.largestRectangleArea(b), 4);
vector<int> c{1, 1, 1, 1}; // 等高要能连成一片
CHECK_EQ(s.largestRectangleArea(c), 4);
vector<int> d{6, 7, 5, 2, 4, 5, 9, 3};
CHECK_EQ(s.largestRectangleArea(d), 16); // 高 2 撑满 8 根柱子;高>4 的最长段只有 3(→ 12)
vector<int> e{0};
CHECK_EQ(s.largestRectangleArea(e), 0);
vector<int> f{2, 1, 2};
CHECK_EQ(s.largestRectangleArea(f), 3); // 高 1 × 宽 3(中间那根矮柱不阻断底边)