题目描述
左右跑一次单调栈
得到左侧和右侧第一个比自己矮的位置
样例
见题面
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,ans,h[10005],l[10005],r[10005];
stack<int> s;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++){
r[i]=n;l[i]=1;
}
//利用单调栈,找右侧第一个比自己矮的
for(int i=1;i<=n;i++){
if(s.empty()) s.push(i);
else{
if(h[s.top()]<h[i]) s.push(i);
else{
while(!s.empty()&&h[s.top()]>h[i]){
r[s.top()]=i;s.pop();
}
s.push(i);
}
}
}
//同理左侧找
while(!s.empty()) s.pop();//清空栈
for(int i=n;i>=1;i--){
if(s.empty()) s.push(i);
else{
if(h[s.top()]<h[i]) s.push(i);
else{
while(!s.empty()&&h[s.top()]>h[i]){
l[s.top()]=i;s.pop();
}
s.push(i);
}
}
}
//for(int i=1;i<=n;i++) cout<<i<<" "<<l[i]<<" "<<r[i]<<endl;
for(int i=1;i<=n;i++) ans=max((r[i]-l[i])*h[i],ans);
cout<<ans<<endl;
return 0;
}