小A的柱状图

小A的柱状图

这道题主要是是考察栈+结构体（单调栈）。
求最大矩形面积：去枚举每一个矩形块，找到覆盖整个矩形块的最大面积。也就是找到一个矩形块左边比它小的坐标和右边比它小的坐标。

利用单调栈来做：加入矩形块的结构体，维护一个高度单调增的栈，如果前面的栈顶比当前的大，则弹出，直到单调增为止，弹出的矩形宽度之和记录下来，加到新加的矩形块的宽度上，这样就可以确保在此过程中不断的确定其中一些矩形块被覆盖的最大面积。当然，最后栈内还会有元素，最后要加一组0数据来确保栈为空，得出所有的矩形块被覆盖的最大面积；
另外要注意数据范围，要开longlong!!!;

#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long  x;
    long long  y;
}l,z;
const int N=1e6+5;
long long  n,i,w[N],h[N],maxx;
stack<node>s;
int main()
{

    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>w[i];
    }
    for(i=0;i<n;i++)
    {
        cin>>h[i];
    }
    s.push(node{w[0],h[0]});
 for(i=1;i<=n;i++)
 {
    int sum=0;
    while(1)
    {

    if(!s.empty()&&s.top().y>=h[i])
    {
        s.top().x+=sum;
        maxx=max(maxx,s.top().x*s.top().y);
        sum=s.top().x;
        s.pop();

     }
     else
     {
        break;
     }
}
s.push(node{w[i]+sum,h[i]});
 }
 printf("%lld", maxx);
}