基础知识：

这篇博客讲得很清楚了，不再赘述https://blog.csdn.net/wubaizhe/article/details/70136174#commentBox

单调栈主要用于找往左遍历第一个小于它的数的位置或者往右遍历第一个小于它的位置（思想懂了之后，一些简单的变形也就理解了）。

模版代码：

Stack<int> S;
    for(int i=1 ;i<=n ;i++){
        while(S.size() && a[S.top()] >= a[i]) S.pop();

        if(S.empty())     L[i] = 0;
        else              L[i] = S.top();

        S.push(i);
    }

hdu1506和小A的柱形图两道题目基本上是一样的，但是后者比前者多了一个条件,比前者复杂一小丢丢，要用到前缀和数组，所以这里只讲解后一道题。

解题思路

对于当前位置的高度h[i]，向左寻找第一个小于h[i]的高度h[j]，取h[j]的右一个位置，对应高度h[k]（这样就有h[k]≥h[i]）

对于当前位置的高度h[i]，向右寻找第一个小于h[i]的高度h[jj](无需把数组倒置，只需要反向遍历i就行，其他操作和上面相同)，取h[jj]的左一个位置，对应高度h[kk]（这样就有h[kk]≥h[i]）

这样我们就可以得到h[k]≥h[i],h[kk]≥h[i],且k≤i≤kk,那么我们就可以直接用k到kk之间的宽度（前缀和公式）乘以h[i]就是以h[i]为基准能得到的最大的面积了，遍历i求出最大的面积就是答案。

-----------------------update

2020.1.29

学习了这种问题的新的写法，在取出栈顶元素的同时，将取走的栈顶的矩形的宽度加到栈内剩余元素的所占宽度中，产生累积效应。具体实现见代码。

 

ac代码

#include <iostream>
#include <algorithm>
#include <stack>
typedef long long ll;
#define maxn 1000005
using namespace std;
struct{
    ll w,h;
}a[maxn];
ll l[maxn],r[maxn],sumw[maxn]={0};
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].w);
        sumw[i]=sumw[i-1]+a[i].w;
    }
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i].h);
    stack<ll> s;
    for(ll i=1;i<=n;i++)
    {
        while(!s.empty() && a[s.top()].h>=a[i].h)
            s.pop();
        if(s.empty()) l[i]=1;
        else l[i]=s.top()+1;//左侧第一个小于a[i].h的点的右边一个
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(ll i=n;i>=1;i--)
    {
        while(!s.empty() && a[s.top()].h>=a[i].h)
            s.pop();
        if(s.empty()) r[i]=n;
        else r[i]=s.top()-1;//右侧第一个小于a[i].h的点的左边一个
        s.push(i);
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        cout<<(sumw[r[i]]-sumw[l[i]-1])*a[i].h<<endl;
        ans=max(ans,(sumw[r[i]]-sumw[l[i]-1])*a[i].h);
    }
    printf("%lld\n",ans);
    return 0;
}

----------update版代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll h[maxn], a[maxn], s[maxn], w[maxn];
int n;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%lld", &h[i]);
    ll ans = 0;
    int p = 0;
    h[n+1] = 0;
    for(int i = 1; i <= n+1; i++)
    {
        if(h[i]>s[p]) s[++p] = h[i], w[p]=a[i];
        else
        {
            int wid = 0;
            while(s[p]>h[i])
            {
                wid += w[p];
                ans = max(ans, wid*s[p--]);
            }
            s[++p] = h[i];
            w[p] = wid+a[i];
        }
    }
    printf("%lld\n", ans);
    return 0;
}