小A的柱状图

题目描述

柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。 ![在这里插入图片描述]

分析：

题目要求要找出上述图形中面积最大的矩形，那么以h[i]为高，分别找到h[i]左边和右边第一个小于h[i]的柱，那么h[i]为高形成的矩形的面积就是，h[i]*底边，找左右柱的过程可以依靠单调栈，存左右柱的下标，底边可以用前缀和。

代码：

#include<iostream>
using namespace std;
typedef long long ll;                                       //
int n,a[1000005];                                           //2 1 4 5 1 3 4
ll h[1000005],sum[1000005],l[1000005],r[1000005];           //1 2 3 4 5 6 7 8
ll solve(){ 
	for(int i=n;i>=1;--i){
		int flag=i+1;
		while(flag<=n&&h[i]<=h[flag])    //寻找右边第一个小于h[i](中间无断点)的元素的下标 
			flag=r[flag];
		r[i]=flag;
	}
	//for(int i=1;i<=n;++i) 
	//	printf("r[%d] = %d\n",i,r[i]);
	for(int i=1;i<=n;++i){
		int flag=i-1;
		while(flag>0&&h[i]<=h[flag])
			flag=l[flag];
		l[i]=flag;
	}
	//for(int i=1;i<=n;++i)
	//	printf("l[%d] = %d\n",i,l[i]);
	sum[1]=a[1];
	for(int i=2;i<=n;++i)               //用前缀和做计算矩形面积的准备 
		sum[i]=sum[i-1]+a[i];
	ll ans=0,msum=0; 
	for(int i=1;i<=n;++i){
		msum=h[i]*(sum[r[i]-1]-sum[l[i]]);
		//printf("i = %d\n",msum);
		if(msum>ans)
			ans=msum;
	}
	return ans;
} 
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
        cin>>h[i];
    ll ans;
    ans=solve();
    cout<<ans;
}

总结:

单调栈和前缀和