题目描述
单调栈
https://www.acwing.com/solution/content/50517/
基础上左右各一次两次
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
const int M = 100010;
int l[M],r[M],h[M];
/*int s[M];*/
stack<int> sl,sr;
int main()
{
int n;
while(scanf("%d",&n),n){
for (int i = 1; i <= n; i ++ )scanf("%d",&h[i]);
//前后段置为-1,到达边界
h[0] = h[n+1] = -1;
sl.push(0);
for(int i = 1;i<=n;i++){
while(h[i] <= h[sl.top()])sl.pop();
l[i] = sl.top();
sl.push(i);
}
sr.push(n+1);
for (int i = n; i > 0; i -- ){
while(h[i] <= h[sr.top()])sr.pop();
r[i] = sr.top();
sr.push(i);
}
/* int t = 0;
s[0] = 0;
for(int i = 1;i<=n;i++){
while(h[i] <= h[s[t]])t--;
l[i] = s[t];
s[++t] = i;
}
t = 0;
s[0] = n+1;
for (int i = n; i > 0; i -- ){
while(h[i] <= h[s[t]])t--;
r[i] = s[t];
s[++t] = i;
}*/
long long res = 0;
for (int i = 1; i <= n; i ++ )
res = max(res,(long long)h[i] * (r[i] - l[i]-1));
printf("%lld\n",res);
}
return 0;
}