[POJ][2559][单调栈] Largest Rectangle in a Histogram

题目大意：

给出一个整数n，表示有n个宽为1的矩形。紧接着输入n个整数，表示每个矩形的高，要求输出最大连续矩形的面积。

思路：

单调栈。

代码：

#include
#include
#include
using namespace std;
struct point
//将矩形的高度和位置封装在结构体中。 
{
    int val;
    //矩形高度的值。 
    int pos;
    //pos表示矩形在序列中的位置。 
}height[100001];
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        stack s;
        for(int i=0;iarea?max:area;
                height[i].pos=s.top().pos;
                //这一步很微妙，要了解单调栈在本题中的几何意义。
                //循环里的这几步操作实际上相当于将矩形i重新放置到左边第一个比它小的矩形前， 
                //并计算矩形i右边第一个矩形到循环开始前的栈顶矩形的最大连续面积。
                //而对矩形i的放置操作就体现在了对height[i].pos的更改上。 
                s.pop();
            }
            s.push(height[i]);
        }
        printf("%I64d\n",max);
    }
}