AcWing 131. 直方图中最大的矩形
原题链接
简单
作者:
小猫你可以吃芝士汉堡
,
2024-03-25 09:47:41
,
所有人可见
,
阅读 3
单调栈求直方图最大矩形
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
LL h[N];
int stk[N], top;
int l[N], r[N];
int main()
{
while(scanf("%d", &n) != -1 && n)
{
for(int i = 1;i <= n;i ++) scanf("%lld", &h[i]);
h[0] = h[n + 1] = -1; // 边界哨兵,处理边界情况
// 找左边第一个比他小的值
top = 0;
stk[++ top] = 0;
for(int i = 1;i <= n;i ++)
{
while(h[stk[top]] >= h[i]) top --;
l[i] = stk[top];
stk[++ top] = i;
}
// 找右边第一个比它小的值
top = 0;
stk[++ top] = n + 1;
for(int i = n;i ;i --)
{
while(h[stk[top]] >= h[i]) top --;
r[i] = stk[top];
stk[++ top] = i;
}
LL res = 0;
for(int i = 1;i <= n;i ++)
res = max(res, h[i] * (r[i] - l[i] - 1));
printf("%lld\n", res);
}
return 0;
}