传送门
题意
直方图是在公共基线处对齐的一系列矩形组成的多边形,各矩形具有相同的宽度,但可以有不同的高度,求最大矩形的面积
例如
阴影部分即最大面积
求出公共基线处对齐的最大对齐矩形
数据范围
(1leq n leq 10^{5})
(0 leq h_{i} leq 10^{9})
题解
建立一个递增单调栈,保存高度,以及这个之前所有比它大的矩形的宽度之和
扫描所有的矩形进行如下操作
-
当前矩形的高度比栈顶矩形高,直接进栈
-
当前小于栈顶就累计所有取出的矩形的宽度之和,每弹出一个矩形,更新一次答案,
-
最后将当前矩形入栈,并保存左边所有小于其高度的矩形的宽度之和
如果末尾存在连续相同的不会有更新答案的操作,
需要增加一个高度为(0)的矩形在(n+1)的位置,处理末尾连续相同高度的矩形
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, a, n) for(int i = a; i < n; i ++)
const int N = 1e5 + 10;
int n;
int h[N], wid[N];
int stk[N], t;
void solve() {
ll ans = 0;
t = 0;
memset(stk, 0, sizeof stk);
rep(i, 1, n + 1) scanf("%d", &h[i]);
h[n + 1] = 0;
rep(i, 1, n + 2) {
if(h[i] > stk[t]) {
stk[++t] = h[i];
wid[t] = 1;
}
else {
int width = 0;
while(stk[t] > h[i]) {
width += wid[t];
ans = max(ans, (ll)stk[t] * width);
t --;
}
stk[++t] = h[i];
wid[t] = width + 1;
}
}
printf("%lld
", ans);
}
int main() {
while(scanf("%d", &n) && n)
solve();
}