因为最后reverse了一次,所以i代表的是r数组的下标,自己觉得不太习惯就再reverse一次。
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int h[N], q[N], l[N] , r[N];
int n;
void get(int bound[N]){
int tt = 0;q[0] = 0;
for(int i = 1 ; i <= n ; i++){
while(tt && h[q[tt]] >= h[i]) tt--;
bound[i] = q[tt];
q[++tt] = i;
}
return;
}
int main(){
while(cin >> n, n){
for(int i = 1 ; i <= n ; i++) scanf("%d", &h[i]);
get(l);
// for(int i = 1 ; i <= n ; i++) cout<<l[i]<<' ';
reverse(h + 1, h + 1 + n);
get(r);
reverse(h + 1, h + 1 + n);
LL res = 0;
for(int i = 1 , j = n ; i <= n ; i++,j--) res = max(res, h[i] * (n + 1 - r[j] - l[i] - 1ll));
cout<<res<<endl;
}
return 0;
}