AcWing 131. 直方图中最大的矩形
原题链接
简单
作者:
kacila
,
2024-04-09 11:11:24
,
所有人可见
,
阅读 1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n;
LL a[N], l[N], r[N];
stack<int> st;
int main()
{
while (cin >> n, !(n == 0))
{
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
while(st.size())st.pop();
for (int i = 1; i <= n; i++)
{
while (st.size() && a[st.top()] >= a[i])
st.pop();
if (st.size() == 0)
l[i] = 0;
else
l[i] = st.top();
st.push(i);
}
while (st.size())
st.pop();
for (int i = n; i >= 1; i--)
{
while (st.size() && a[st.top()] >= a[i])
st.pop();
if (st.size() == 0)
r[i] = n + 1;
else
r[i] = st.top();
st.push(i);
}
// for (int i = 1; i <= n; i++)
// {
// cout << l[i] << ' ';
// }
// cout << endl;
// for (int i = 1; i <= n; i++)
// {
// cout << r[i] << ' ';
// }
LL ans = 0;
for (int i = 1; i <= n; i++)
{
ans = max(a[i] * (r[i] - l[i] - 1), ans);
}
cout << ans << endl;
}
return 0;
}