AcWing 131. 直方图中最大的矩形 STL Stack实现
原题链接
简单
作者:
Snrise
,
2024-03-31 15:39:11
,
所有人可见
,
阅读 1
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#define int long long
#define endl '\n'
using namespace std;
const int N = 100010;
int h[N], l[N], r[N];
int n;
signed main(void)
{
std::ios::sync_with_stdio(false);
while (cin >> n, n)
{
for (int i = 1; i <= n; i++)
{
cin >> h[i];
}
h[0] = h[n + 1] = -1;
stack<int> s;
s.push(0);
for (int i = 1; i <= n; i++)
{
while (s.size() && h[s.top()] >= h[i])
{
s.pop();
}
l[i] = s.top();
s.push(i);
}
// for (int i = 0; i < n; i++)
// {
// cout << l[i] << ' ';
// }
s = stack<int>(); // 记得清空之前的栈;
s.push(n + 1);
for (int i = n; i >= 1; i--)
{
while (s.size() && h[s.top()] >= h[i])
{
s.pop();
}
r[i] = s.top();
s.push(i);
}
// for (int i = 0; i < n; i++)
// {
// cout << r[i] << ' ';
// }
int res = 0;
for (int i = 1; i <= n; i++)
{
res = max(res, h[i] * (r[i] - l[i] - 1));
}
cout << res << endl;
}
return 0;
}