单调栈

本题要求找出最大矩形的面积。从基本概念入手，给定长（本题也可以说“高”）和宽便可以确定一个矩形的面积，所以我们的任务便是找到高和宽。

首先，要尝试所有的区间很显然是不可能的；可以发现对于每一段区间，矩形的宽都可以用a数组的前缀和求出来，所以我们的任务重心转移到了矩形的高上。

求高便是求一段区间内h的最小值，这里容易想到单调队列栈。很显然此处不能用单调队列处理，因为并没有指定矩形的宽占多少区间，所以采用单调栈处理。
单调栈：求数组某个位置的值在哪个最大区间（相邻）是最值。
此时只要找到每个位置的在哪个最大区间是最小值即可，因为一旦超过这个区间，要么是超过了边界，要么是存在一个h[i]小于该高，此时高发生了改变。

最后简单概括：该方法是在每个h[i]都为高时，找到其对应的最大的宽，即可找到最大面积。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e6+9;
const ll maxx=1e12+9;

int n,a[maxn],h[maxn];
int sum[maxn];
stack<int> st;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    ll ans=0;
    st.push(0);
    for(int i=1;i<=n;i++)
    {
        while(h[i]<h[st.top()])
        {
            int H=h[st.top()]; st.pop();
            ans=max(ans,1ll*(sum[i-1]-sum[st.top()])*H);
        }
        st.push(i);
    }
    while(st.size()>1)
    {
        int H=h[st.top()]; st.pop();
        ans=max(ans,1ll*(sum[n]-sum[st.top()])*H);
    }
    printf("%lld\n",ans);
}