单调栈模板——Acwing131. 直方图中最大的矩形
2026/4/9大约 4 分钟
单调栈模板——Acwing131. 直方图中最大的矩形
题目
直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度，但可以具有不同的高度。
例如，图例左侧显示了由高度为 2,1,4,5,1,3,3 的矩形组成的直方图，矩形的宽度都为 11：
通常，直方图用于表示离散分布，例如，文本中字符的频率。
现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。
图例右图显示了所描绘直方图的最大对齐矩形。
输入格式
输入包含几个测试用例。
每个测试用例占据一行，用以描述一个直方图，并以整数 nn 开始，表示组成直方图的矩形数目。
然后跟随 n 个整数 h1，…，hn。
这些数字以从左到右的顺序表示直方图的各个矩形的高度。
每个矩形的宽度为 1。
同行数字用空格隔开。
当输入用例为 n=0 时，结束输入，且该用例不用考虑。
输出格式
对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。
每个数据占一行。
请注意，此矩形必须在公共基线处对齐。
数据范围
1≤n≤100000,0≤hi≤1000000000
输入样例：
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0输出样例：
8
4000c++题解
单调栈解法
#include<bits/stdc++.h>
using namespace std;
const int N= 100010;
int n,h[N],l[N],r[N],q[N];
int main(){
while(cin>>n&&n){
h[0] = h[n+1] = -1;
for(int i = 1;i<=n;i++)cin>>h[i];
int tt = 0;
q[0] = 0;
for(int i = 1;i<=n;i++){
while(h[i]<=h[q[tt]])tt--;
l[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = n+1;
for(int i = n;i>0;i--){
while(h[i]<=h[q[tt]])tt--;
r[i] = q[tt];
q[++tt] = i;
}
long long res = 0;
for(int i = 1;i<=n;i++){
res = max(res,(long long )(r[i]-l[i]-1)*h[i]);
}
cout<<res<<endl;
}
}笛卡尔树解法
AcWing 131. 直方图中最大的矩形（笛卡尔树解决） - AcWing
Java题解
栈存下标
import java.util.Scanner;
/**
* @see 单调栈 https://www.acwing.com/problem/content/133/
*/
public class Main {
static final int N = 100010;
static int[] height = new int[N];
static int[] left = new int[N];
static int[] right = new int[N];
static int[] q = new int[N];
//用数组模拟栈的时候，要实现“栈的长度是动态变化的这个特点”，要用另一个存下标的数组来实现
//也就是说栈中元素的长度，是队列的长度
//栈中存的是选入队列的元素的下标，通过下标从原数组中获得值
//这样做还有一个好处；如果存值，不可能通过该值找回该值原来的下标，
//按这种方式存储，还可以记录该值的下标
//且使用时可以当做存值的栈使用
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
if (n == 0) {
break;
}
// int[] height = new int[n + 2];
// int[] left = new int[n + 2];
// int[] right = new int[n + 2];
// int[] q = new int[n + 2];
height[0]=height[n+1] =-1;
for (int i = 1; i <= n; i++) {
height[i] = sc.nextInt();
}
int tt = 0;
q[0] = 0;
for(int i = 1; i <=n; i++) {
while (height[i]<=height[q[tt]]){
tt--;
}
left[i] = q[tt];
q[++tt] = i;
}
tt=0;
q[0] = n+1;
for (int i =n;i>0;i--){
while (height[i]<height[q[tt]]){
tt--;
}
right[i] = q[tt];
q[++tt] = i;
}
long res = 0;
for(int i = 1; i <=n; i++) {
res = Math.max(res,(long) height[i]*(right[i]-left[i]-1));
}
System.out.println(res);
}
}
}栈存元素
import java.util.Scanner;
/**
* @see 单调栈 https://www.acwing.com/problem/content/133/
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
if (n == 0) {
break;
}
int[] height = new int[n + 2];
int[] widthArr = new int[n + 2];
int[] q = new int[n + 2];
for (int i = 1; i <= n; i++) {
height[i] = sc.nextInt();
}
int tt;
long res = 0;
tt = height[n + 1] = 0;
for (int i = 1; i <= n + 1; i++) {
if (height[i] > q[tt]) {
q[++tt] = height[i];
widthArr[tt] = 1;
} else {
int width = 0;
while (height[i] < q[tt]) {
width += widthArr[tt];
res = Math.max(res, (long) width * q[tt]);
tt--;
}
q[++tt] = height[i];
widthArr[tt] = width + 1;
}
}
System.out.println(res);
}
}
}python题解
nums = []
while True:
try:
line = [int(x) for x in input().split()]
if line[0] > 0:
nums.append(line[1:])
except:
break
def max_rectangle_area(height) -> int:
n = len(height)
height = [-1] + height + [-1]
res = 0
incstk = []
for i in range(n + 2):
while incstk and height[incstk[-1]] > height[i]:
window_min_height = height[incstk.pop(-1)]
window_L = incstk[-1] + 1
window_R = i - 1
window_area = (window_R - window_L + 1) * window_min_height
res = max(res, window_area)
incstk.append(i)
return res
for height in nums:
print(max_rectangle_area(height))写法二
# 接受输入
while True:
line = input()
if line == '0':
break
items = list(map(int, line.split()))
n = items[0]
heights = items[1:]
stack = [-1]
ans = 0
for i in range(n):
if heights[i] > heights[stack[-1]]:
stack.append(i)
else:
while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
ans = max(ans, heights[stack.pop()] * (i - stack[-1] - 1))
stack.append(i)
while stack[-1] != -1:
ans = max(ans, heights[stack.pop()] * (len(heights) - stack[-1] - 1))
print(ans)参考博客
AcWing 131. 直方图中最大的矩形--单调递增栈--c++/python3 - AcWing
AcWing 131. 直方图中最大的矩形（笛卡尔树解决） - AcWing
AcWing 131. 直方图中最大的矩形 (STL) - AcWing