AcWing 131. 直方图中最大的矩形
原题链接
简单
作者:
tire
,
2024-07-23 09:24:52
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int h[N];
int stk[N],top;
int n;
int l[N],r[N];
typedef long long ll;
ll work(int h[])
{
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>=1;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,(ll)h[i] * (r[i] - l[i] - 1));
return res;
}
int main()
{
while(cin >> n,n){
for(int i = 1;i<=n;i++) cin >> h[i];
cout << work(h) << endl;
}
return 0;
}