C++(g++ 7.5.0) 解法, 执行用时: 33ms, 内存消耗: 1584K, 提交时间: 2023-07-24 10:40:42

#include<bits/stdc++.h>
using namespace std;
long long a[1000001],p,w[1000001],s[1000001];
int main(){
	long long n,ans;
	while(scanf("%lld",&n)&&n){
		ans=0;
		for(register int i=1;i<=n;++i)scanf("%lld",&a[i]);
		a[n+1]=p=0;
		for(register int i=1;i<=n+1;++i){
			if(a[i]>s[p])s[++p]=a[i],w[p]=1;
			else{
				long long width=0;
				while(s[p]>a[i])width+=w[p],ans=max(ans,width*s[p]),--p;
				s[++p]=a[i],w[p]=width+1;
			}
		}
		printf("%lld\n",ans);
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 99ms, 内存消耗: 1172K, 提交时间: 2022-08-07 18:52:57

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
ll h[N];
int main()
{
	int n;
	while(cin>>n){
		if(n==0)break;
		stack<int>st;
		for(int i=0;i<n;i++)cin>>h[i];
		ll ans=0;
		h[n]=0;
		for(int i=0;i<=n;i++){
			while(!st.empty()&&h[st.top()]>=h[i]){
				int t=st.top();
				st.pop();
				ans=max(ans,h[t]*(st.empty()?i:(i-st.top()-1)));
			}
			st.push(i);
		}
		cout<<ans<<endl;
	}
	
	return 0;
}