小A的柱状图

题意：
给你一个柱状图，有n根柱子，给予你每根的宽度和高度，求柱状图的最大矩形面积？

思路：
单调栈，维护一个单调递增的栈，维护高度和左边界。
当h[i]>栈顶元素的高度时入栈，左边界不变。
当h[i]<栈顶元素的高度时，栈顶元素出栈，并计算以该栈顶元素高度为一条边的矩形最大面积（既（右边界-左边界） * 高度）。直到栈为空或h[i]>栈顶元素的高度时停止。将其入栈。如果栈为空，左边界不变，否则更新左边界。
当h[i]=栈顶元素的高度时,开始下一个元素。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <map>

#define inf 1000000007
#define eps 0.00000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn=100005;

inline int read()
{
    char c=getchar();
    int f=1, x=0;
    while(c>'9'||c<'0')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f*x;
}

ll d[1000005], a[1000005];

struct w
{
    ll s, x;
}w[1000005];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        ll di;
        scanf("%lld",&di);
        d[i]=d[i-1]+di;
    }
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
    }
    int p=0;
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]==w[p-1].x)
        {
            continue;
        }
        if(p==0||w[p-1].x<a[i])
        {
             w[p].s=d[i];
             w[p].x=a[i];
             p++;
             continue;
        }
        while(p!=0&&w[p-1].x>a[i])
        {
            ans=max(ans,(d[i]-w[p-1].s)*w[p-1].x);
            p--;
        }
        w[p].x=a[i];
        p++;
    }
    while(p!=0)
    {
         ans=max(ans,(d[n]-w[p-1].s)*w[p-1].x);
         p--;
    }
    cout << ans << endl;
    return 0;
}