Week5作业-A-最大矩形

目录

• 1.题意
• 2.样例
• 3.解题思路
• 4.总结
• 5.AC代码

1.题意

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

2.样例

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

Sample Output

8

4000

3.解题思路

1. 由于此题n为1e5所以n^2的复杂度是不能接受的，又因为其为全局单调性即寻找某一小矩形左边和右边第一个高度比它小的，所以考虑单调栈（O(n)
2. 先寻找右边第一个比它小的，即维护一个单调递增栈当栈顶元素比新元素大时更新其R值为i-1（即右边第一个比它小的下标），同时删除栈顶元素维护其单调性，最后对仍在栈中的元素进行处理，即它们右边没有比它小的所以R值均更新为n-1
3. 对于寻找左边第一个比它小的元素，与右边同理，只需将数组反向遍历，更新R值时为i+1，同样最后对仍在栈中的元素进行处理，即它们左边没有比它小的所以L值均更新为0

4.总结

1. 此题是对单调栈的简单考察，要掌握单调栈的思想
2. 此题要注意ai的范围为0-1e9所以不能用int来定义数组和最后答案要用long long
3. 数据不仅关注n的范围确定复杂度，还要关注ai范围选择合适的类型

5.AC代码

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
void stackr(vector<long long>& v,int *r)
{
	stack<int>s;
	for(int i=0;i<v.size();i++)
	{
		while(!s.empty()&&v[s.top()]>v[i])
		{
			r[s.top()]=i-1;
			s.pop();
		}
		s.push(i);
	}
	while(!s.empty())
	{
		int fr=s.top();
		r[fr]=v.size()-1;
		s.pop();
	}
}
void stackl(vector<long long>& v,int *l)
{
	stack<int>s;
	for(int i=v.size()-1;i>=0;i--)
	{
		while(!s.empty()&&v[s.top()]>v[i])
		{
			l[s.top()]=i+1;
			s.pop();
		}
		s.push(i);
	}
	while(!s.empty())
	{
		int fr=s.top();
		l[fr]=0;
		s.pop();
	}
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr);
	int n,h;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0) break;
		vector<long long> v;
		int r[100005]={0};
		int l[100005]={0};
		for(int i=0;i<n;i++)
		{
			cin>>h;
			v.push_back(h);
		}
		stackr(v,r);
		stackl(v,l);
		long long ma=0;
		for(int i=0;i<n;i++)
		{
			long long sum=(r[i]-l[i]+1)*v[i];
			ma=max(ma,sum);
		}
		cout<<ma<<endl;
		for(int i=0;i<v.size();i++)
		{
			v.pop_back();
		}
	}
	return 0;	
}