单调栈求助
查看原帖
单调栈求助
127925
Kio_楼主2020/11/19 18:31

一直WA,求大佬答疑QwQ

#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e5+20;
int n,num[maxn];
struct pt{
	ll h,w;
}stack[maxn];
ll ans;
int cnt=0;
inline ll max(ll a,ll b){return a>b?a:b;}
int read(){
	int num=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while('0'<=c&&c<='9') num = num*10+(c&15), c=getchar();
	return num;
}
int main(){
	while(1){
		n=read();
		if(!n) return 0;
		ans=0;
		num[n+1] = -1;
		for(int i=1;i<=n;i++) num[i] = read(), stack[i].h = 0, stack[i].w = 0;
		for(int i=1;i<=n+1;i++){
			if(num[i] >= stack[cnt].h) stack[++cnt].h = num[i], stack[cnt].w = 1;
			else{
				ll width=0;
				while(num[i] < stack[cnt].h && cnt) ans = max(ans, (width + stack[cnt].w) * stack[cnt].h), width++, stack[cnt].h = 0, stack[cnt].w = 0, cnt--;
				stack[++cnt].h = num[i], stack[cnt].w = width+1;
			}
		}
		printf("%lld\n",ans); 
	}
}
2020/11/19 18:31
加载中...