AcWing 131. 直方图中最大的矩形
原题链接
简单
#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 1e5+100;
long long h[N];
int l[N],r[N];
int main()
{
int n;
while(scanf("%lld",&n), n!=0) {
for (int i = 1; i <= n; i ++ ) scanf("%lld", h+i);//注意: scanf有个坑,如果是 long long 要用 %lld ,调bug调变天
//读入 高度数组后 ,开始用单调队列求解
stack<int> stk;
//stk.push(0);
h[0] = h[n+1] = -1;
//设置哨兵
for(int i=1;i<=n;++i) {
while(stk.size() && h[i] <= h[stk.top()]) stk.pop();
l[i] = stk.size()? stk.top(): 0;
stk.push(i);
}
while(stk.size()) stk.pop();
stk.push(n+1);
for(int i=n;i;--i) {
while( stk.size() && h[i] <= h[stk.top()]) stk.pop();
r[i] = stk.size()? stk.top(): n+1;
stk.push(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;
}
return 0;
}