最大矩形

题意：

给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。

Input

输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 <= n <= 100000. 然后接下来n个整数h1, ..., hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。 测试数据以0结尾。

Output

对于每组测试数据输出一行一个整数表示答案。

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8 

4000

我的题解：

本题暴力解比较复杂，可以利用单调（递增）栈解决：

遍历输入的数据，如果栈为空或者栈顶元素比要压入栈的元素小，就将元素压入栈。

否则栈顶元素出栈，同时计算以栈顶元素值为高的矩形的面积，

其宽度为要压入栈的元素的下标i减去栈顶元素出栈后的栈顶元素的下标。

在所有数据遍历完成之后，如果栈中还有元素，将它们全部出栈，并计算以其为高的矩形的面积。

输出最大的矩形面积。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[100010],s[100010],w[100010],p=0;
        
    while(n!=0)
    {
        long long 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,(long long)width*s[p]);
                    p--;
                }
                s[++p]=a[i],w[p]=width+1;
            }
        }
        cout<<ans<<endl;
        cin>>n;
    }
    return 0;
}

 注：由于输入数据有多组，所以需要注意每次都要初始化。