题目链接

题目思路

模板题

用单调栈预处某个点左边和右边比它本身大的范围即可

假设\(h[i]\)为矩阵高度即可，然后计算即可

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=100000+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m;
int h[maxn];
int l[maxn],r[maxn];
signed main(){
    while(scanf("%d",&n)!=-1&&n){
        for(int i=1;i<=n;i++){
            scanf("%d",&h[i]);
        }
        ll ans=0;
        stack<int> sta;
        for(int j=1;j<=n;j++){
            while(!sta.empty()&&h[sta.top()]>=h[j]){
                sta.pop();
            }
            l[j]=sta.empty()?0:sta.top();
            sta.push(j);
        }
        while(!sta.empty()) sta.pop();
        for(int j=n;j>=1;j--){
             while(!sta.empty()&&h[sta.top()]>=h[j]){
                sta.pop();
            }
            r[j]=sta.empty()?n+1:sta.top();
            sta.push(j);
        }
        for(int j=1;j<=n;j++){
            ans=max(ans,1ll*(r[j]-l[j]-1)*h[j]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}