一道单调栈的基础题，我们建立一个单调上升的栈，当一个矩形被扫描时，如果他的高度大于栈顶就直接入栈，否则就不断取出栈顶，直到栈空或者栈顶小于当前矩形，在出栈的同时，我们累计被弹出的矩形宽度之和，每次弹出一个矩形，我们就用他的高度乘累计的宽度更新答案，出栈结束后，我们把一个高度为当前高度，宽度为累计宽度的新矩形入栈。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 typedef long long ll; 5 using namespace std; 6 ll n,ans,a[100010],s[100010],p,w[100010]; 7 int main() { 8 while(scanf("%lld",&n)&&n) { 9 ans=0; 10 memset(s,0,sizeof(s)); 11 memset(w,0,sizeof(w)); 12 memset(a,0,sizeof(a)); 13 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); 14 for(int i=1;i<=n+1;i++) { 15 if(a[i]>s[p]) { 16 s[++p]=a[i]; 17 w[p]=1; 18 continue ; 19 } 20 ll wi=0; 21 while(s[p]>a[i]) { 22 wi+=w[p]; 23 ans=max(ans,wi*s[p]); 24 p--; 25 } 26 s[++p]=a[i]; 27 w[p]=wi+1; 28 } 29 printf("%lld ",ans); 30 } 31 return 0; 32 }