题目大意

有n个宽度为1，高度分别为h1,h2……hn的长方形从左到右依次排列组成的柱状图，问里面包含的长方形的最大面积是多少。
限制条件
1<=n<=100000
0<=hi<=10^9

http://poj.org/problem?id=2559 原题目链接

方法

单调栈作为辅助栈
依次遍历每个矩形条，并且按照以下顺序维护这个栈：设在栈里的元素从上到下的值为xi，那么xi>x(i+1)且h（xi）>h(x(i+1))，xi为每个矩形条的索引。

如果我们能知道一个矩形条向左向右最远能延伸多远，我们就能计算出以该矩形条为高的矩形面积了！我们怎么知道向左向右能延伸多远？观察下面几种情况：

情况1：第i个矩形比右边相邻的第i+1个矩形高，如下图所示。意味着，以height[i]为高的矩形的右边界就是第i个矩形，因为右边界不能更右了（废话），也不会在左边（向左只会让矩形面积减小）。所以在这种情况下，我们可以立即确定以第i个矩形的高度height[i]为高度的最大矩形面积的右边界。
情况2：第i个矩形比左边相邻的第i-1个矩形高，如下图所示。意味着，以height[i]为高的矩形的左边界就是第i个矩形，因为左边界不能更左了（废话），也不会出现在右边（因为向右只会另矩形面积减小）。所以在这种情况下，我们立即就可以确定以第i个矩形的高度height[i]为高度的最大举行面积的左边界。
现在，我们依次遍历各个矩形条，遍历过的矩形条压入栈中保存，则不难发现下面的现象：

如果当前矩形条的高度高于栈顶的矩形条的高度，对应上面的情况2，我们可以立即得出，当前矩形一定是以它为高的矩形的左边界。那么现在我们还不能确定其右边界，所以除了入栈什么都不用做，如下图所示：

如果当前矩形条的高度小于或等于栈顶矩形条的高度，对应上面的情况1，我们可以立即得出：栈顶的矩形一定是以它为高的矩形的右边界所以，我们可以立刻得*到以栈顶的矩形条高度为高度的最大矩形的面积（下图中带颜色的两个矩形）！既然我们算出了前一个条最大矩形的面积，那么也就没必要再留着它了。所以，可以放心把它删掉，或者说合并。


按照上述操作遍历完所有矩形条之后，栈中的矩形一定是下面这个样子。（栈里面所有的条肯定是按照高度依次递增的）

此时，对于任何一个矩形条，我们可以确定，它的右边界一定是整个栈里所保留的条形图的最右边界，而它的左边界一定是它这个条自己的左边界，所以，剩余的矩形条也可以立即算出其对应的最大矩形的面积

其实，只需要在所有的矩形条最后添加一个高度为0的虚拟矩形条，可以省略上面的两小步。这个虚拟矩形条起收割作用。

#include <iostream>
#include <stack>
#include <cstring>
#include <stdio.h>
using namespace std;
int height[100005];
int main(){
    int n;
	scanf("%d",&n);	
	while(n!=0){
		memset(height,0,n+10);//初始化height数组 
	    stack <int> st;//定义一个st栈，用于存放每个矩阵长度单调递增下标索引 
		long long h,w;
		long long maxArea=0;
		int x,j;
		for(j=0;j<n;j++)
		    scanf("%d",&height[j]);
        height[j]=0;//加高度为0的矩形条用于收割 
        for(int i=0;i<=n;i++){
    	    if(st.empty()||height[st.top()]<height[i])//无法确定栈顶矩阵右边界，继续压栈 
                st.push(i);
            else{
        	    while(!st.empty()&&height[i]<=height[st.top()])//确定当前栈顶元素右边界，出栈算面积 
				{			        
        		    h=height[st.top()];
        		    st.pop();
        		    w=st.empty() ? i : i-(st.top()+1) ;//栈为空返回长度i，非空返回长度为当前下标减去栈顶矩阵的位置+1； 
        		    maxArea=max(maxArea,h*w);//比较每一个子矩阵的面积，选出最大的 
			}
			st.push(i);//当前矩阵条进栈 
		}
	}	
	printf("%lld\n",maxArea);
	scanf("%d",&n);
	}
	return 0;      
}

参考博客：https://www.cnblogs.com/boring09/p/4231906.html
只能说膜拜大佬的解题思路哇！