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;	
}