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

1.png

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
实现思路：
依据题意，对于每个小矩形我们需要向前向后分别找到第一个比它低的矩形，此时得到的便为其所能构成的最大矩形，因此我们需要构建单调递增栈来储存当前遍历到的满足条件的最大矩形。最后依次从栈中找出各部分最大值，取最大面积输出。

实现代码如下：

#include<cstdio>
#include<iostream>
#include<stack> 
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;

struct tran{
    long long high;
     int index;
}t[maxn];
int main()
{
    while(true)
    {
        int n;
        cin>>n;
        if(n==0)break;
        stack<tran>s;
        long long ans=0;
        for(int i=1;i<n+1;i++)
        {
            scanf("%lld",&t[i].high);
            t[i].index=i;
            int index;//当前小矩形位置
            int left=i;//最左侧端点
            long long h;//当前小矩形高度

            //查找当前最大矩形
            while(!s.empty()){
                index=s.top().index;
                h=s.top().high;
                if(h>=t[i].high)
                {
                    s.pop();
                    left=index;
                    ans=max(ans,h*(i-left));
                }
                else
                {
                    break;
                }
              }s.push({t[i].high,left});//当前最大矩形入栈
        }
               //找出栈中最大矩形面积
        while(!s.empty()){
            int index;
            int left;
            long long h;
            index=s.top().index;
            h=s.top().high;
                s.pop();
                left=index;
                ans=max(ans,h*(n+1-left));
            }
        printf("%lld\n",ans);
    }
    
  
    return 0;
}

小结:利用单调递增栈(单调递减栈)处理问题可以以O(n)的复杂度处理针对每个数，寻找它和它左 / 右边第一个比它大 / 小的数的值，以及相距多少个数的问题。