AcWing 131. 直方图中最大的矩形
原题链接
简单
作者:
周赛坐牢选手
,
2021-12-17 09:58:16
,
所有人可见
,
阅读 212
//大于等于栈顶时加长度,同时弹栈 小于时直接进栈 最后把所有长度*最后的
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
vector<PII>a;
LL ans;
int n, t;
//栈是递增的
void v_stack(int t)
{
int wide = 0;
while(a.size() && a.back().x >= t)
{
wide += a.back().y;
ans = max(ans, 1ll * wide * a.back().x);
a.pop_back();
}
a.push_back({t, wide + 1}); //记录前面的长度
}
int main()
{
while(cin >> n && n)
{
ans = 0;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &t);
v_stack(t);
}
v_stack(-1);
printf("%lld\n", ans);
}
return 0;
}