CCF CSP 201312-3 最大的矩形

数组a[]：依次存储每个矩形的高度

数组s[]：作为辅助栈，保存若干矩形，s中这些矩形的高度是依次不减的

数组w[]：存储栈中矩形的“宽度”

这里的“宽度”是指：在数组a中，某矩形的左边，高度≥该矩形高度的矩形的个数

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[1001],s[1001],w[1001],p=0;
    //从数组下标为1处开始存储，故要开辟1001大小的数组空间
    int ans=0;
    memset(a,0,sizeof(a));
    memset(s,0,sizeof(s));
    memset(w,0,sizeof(w));
    for(int i=1; i<=n; i++) 
        cin>>a[i];
    for(int i=1; i<=n+1; i++)
    {
        if(a[i]>=s[p]) s[++p]=a[i],w[p]=1;
        else
        {
            int 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;
        }
    }
    cout<<ans;
    return 0;
}