栈求解最大矩形

题目描述

给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是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

解题思路

本题的思路较为难想到，小白如果第一次遇到这道题的话可能一下很懵（比如我），但是有经验的人就会瞬间想到思路。要计算最大的矩形面积，就要使得底×高最大。如果确定了底，就要使高尽可能大，如果确定了高，就要使底尽可能大。而本题中可以确定的是高，方法是：可以依次遍历每一个小的矩形，然后向两边扩展，找到第一个小于此高度的点，这便是以这个矩形为高所求得的最大面积，最后将遍历求得的面积取最大值即可。
比较容易想到的是使用栈结构，本来我刚开始在遍历每个矩形都建立一个栈，但是由于时间复杂度的要求很高，后面对代码进行优化，使用一个栈便可以实现，只需要进行适当的出栈操作即可，大大降低了复杂度。

代码

#include<iostream>
#include<stack>
using namespace std;
struct node
{
	int order;//第几块矩形
	long long h;//矩形高度 
};
int n;
node  m[100000];
int r[100000],l[100000];//记录举行的右端点和左端点 
long long ans[100000];
stack<node> t;
int main()
{

	while(cin>>n,n!=0)
	{
		for(int i=0;i<n;i++)
		{
			m[i].order=i;
			cin>>m[i].h;
		}
		    
		for(int i=0;i<n;i++)
		{
			while(!t.empty() && m[i].h<t.top().h)
        	{
				node temp=t.top();
				r[temp.order]=i;//记录对应的区间右端点 
				t.pop();
			}
        	t.push(m[i]);
        }
        //如果栈不为空，则说明栈中元素单调，所有元素的右端点均为n 
        while(!t.empty()) 
        {
        	node temp=t.top();
        	r[temp.order]=n;
        	t.pop();
		}
		for(int i=n-1;i>=0;i--)
		{
			while(!t.empty() && m[i].h<t.top().h)
        	{
				node temp=t.top();
				l[temp.order]=i;//记录对应的区间右端点 
				t.pop();
			}
        	t.push(m[i]);
        }
        //如果栈不为空，则说明栈中元素单调，所有元素的右端点均为n 
        while(!t.empty()) 
        {
        	node temp=t.top();
        	l[temp.order]=-1;
        	t.pop();
		}
		long long max=0;
		for(int i=0;i<n;i++)
		{
			ans[i]=m[i].h*(r[i]-l[i]-1);
			if(ans[i]>max)  max=ans[i];
		}
		cout<<max<<endl;
	}
	return 0;
}