题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
单调栈
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int l[N],r[N];
int h[N];
int n;
int stk[N];
int main()
{
while(cin>>n,n)
{
h[0] = h[n+1] = -1;
for(int i = 1;i<=n;i++)
{
cin >> h[i];
}
stk[0] = 0;
int tt = 0;
for(int i = 1;i<=n;i++)
{
while(h[stk[tt]]>=h[i]) tt--;
l[i] = stk[tt];
stk[++tt] = i;
}
tt = 0;
stk[0] = n + 1;
for (int i = n; i; i -- )
{
while (h[stk[tt]] >= h[i]) tt -- ;
r[i] = stk[tt];
stk[ ++ tt] = i;
}
LL res = 0;
for (int i = 1; i <= n; i ++ )
res = max(res, (LL)h[i] * (r[i] - l[i] - 1));
printf("%lld\n", res);
}
return 0;
}