https://www.acwing.com/video/2649/
也是单调栈问题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 100010;
int h[N];
int l[N], r[N], q[N];
int main(){
int n;
while(cin >> n){
if(n == 0) break;
for(int i = 1; i <= n; i++){
cin >> h[i];
}
h[0] = h[n + 1] = -1; //边界的高度设为-1
int tt = 0; //相当于指针 ,指向栈顶
q[0] = 0;
for(int i = 1; i <= n; i++){
while(h[i] <= h[q[tt]]) tt--;
l[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = n + 1;
for(int i = n; i > 0; i--){
while(h[i] <= h[q[tt]]) tt--;
r[i] = q[tt];
q[++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;
}