题目给一个由几个相连接的矩形组成的多边形，计算多边形包含的最大的矩形的面积。

要求的矩形的高一定是某一个用来组合的矩形的高；如果枚举每个矩形作为高的话，那样长就是这个矩形能向左向右继续延伸矩形的长度了。

所以这题本质也是用单调栈在O(n)计算出每个数作为最小数向左和向右能延伸的最长距离。

1 #include
     
       2 #include
      
        3 using namespace std; 4 #define MAXN 111111 5 int a[MAXN]; 6 int l[MAXN],r[MAXN]; 7 int stack[MAXN],top; 8 int main(){ 9     int n;10     while(~scanf("%d",&n) && n){11         for(int i=1; i<=n; ++i){12             scanf("%d",a+i);13         }14         a[++n]=-1;15         top=0;16         for(int i=1; i<=n; ++i){17             l[i]=r[i]=i;18             while(top && a[stack[top]]>a[i]){19                 l[i]=l[stack[top]];20                 r[stack[top]]=i-1;21                 --top;22             }23             if(top && a[stack[top]]==a[i]) l[i]=l[stack[top]];24             stack[++top]=i;25         }26         long long res=0;27         for(int i=1; i