HDU-1506.Largest Rectangle in a Histogram

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1506
思路：并查集 || 单调栈
思路一、并查集：首先对数组以b[]={值，下标}结构按照从小到大排序，然后从大的开始处理，对于b[i]={val,id}, 比较其id位置左右相邻的值是否大于等于val,若大于等于则将其合并成一个集合，同时记录其集合中元素的个数s，那么当前元素的最大值为 val*s，res取所有元素的最大值即可。

思路二、单调栈：遍历数组，维护单调递增栈，对于当前元素x，其左边元素x0，当x0>x时，将单调递增栈中xi大于等于x的元素出栈，计算xi以x0为最右边界时的最大值，即xi*(xi到x0的个数)，再将x入栈，同时记录其等效为x的元素个数。

Code 并查集:

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pr;

const int MAX_N=1e5+5;
int n;
int a[MAX_N],d[MAX_N];
int id[MAX_N];
pr b[MAX_N];

int Find(int x){
	if(id[x]!=x)	id[x]=Find(id[x]);
	return id[x];
}

void Union(int a,int b){
	d[Find(b)]+=d[Find(a)];
	id[Find(a)]=Find(b);
}

int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n&&n){
		for(int i=1;i<=n;++i)
			id[i]=i,d[i]=0;
		for(int i=1;i<=n;b[i]={a[i],i},++i)
			cin>>a[i];
		a[0]=a[n+1]=-1;
		sort(b+1,b+n+1);
		LL res=0;
		for(int i=n;i>0;--i)
		{
			d[Find(b[i].second)]=1;
			if(b[i].first<=a[b[i].second-1]&&d[b[i].second-1]){
				Union(b[i].second,b[i].second-1);
			}
			if(b[i].first<=a[b[i].second+1]&&d[b[i].second+1]){
				Union(b[i].second,b[i].second+1);
			}
			res=max(res,b[i].first*d[Find(b[i].second)]);
		}
		cout<<res<<endl;
	}
	
	return 0;
}

Code 单调栈：

#include<iostream>
#include<stack>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pr;

int n;
stack<pr> sta;

int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n&&n){
		LL res=0,x,s;
		for(int i=0;i<n;++i)
		{
			cin>>x;
			s=0;
			while(!sta.empty()&&sta.top().first>=x){
				s+=sta.top().second;
				res=max(res,sta.top().first*s);
				sta.pop();
			}
			sta.push({x,s+1});
		}
		s=0;
		while(!sta.empty()){
			s+=sta.top().second;
			res=max(res,sta.top().first*s);
			sta.pop();
		}
		cout<<res<<endl;
	}
	
	return 0;
}