题解 | #小A的柱状图#

我用栈来存每个矩形的下标，而不是高度或者宽度。

#include<bits/stdc++.h> 
using namespace std;
struct node{
	int d,h;
}a[1000001];

long long maxx(long long a,long long b)
{
	if(a>b)return a;
	else return b;
}

int main()
{
	stack<int> s;	
	int n,flag;
	long long max=0,k=0;//k用来累计栈弹出的矩形的宽度的累加 
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].d;
	for(int i=1;i<=n;i++)cin>>a[i].h;
	for(int i=1;i<=n;i++)
	{
		flag=0;
		while(!s.empty() && a[s.top()].h>=a[i].h)
		{
			k+=a[s.top()].d;
			max=maxx( max,(a[s.top()].h)*k );
			s.pop();
			flag=1;
		}
		if(flag==1)
		{
			a[i].d=k+a[i].d;
			k=0;
		}
		s.push(i);
	}
	k=0;
	while(!s.empty())
	{
		k+=a[s.top()].d;
		max=maxx( max , (a[s.top()].h)*(a[s.top()].d) );
		s.pop();
	}
	cout<<max; 
	return 0;
}