Largest Rectangle in a Histogram-题解

查看原题请戳这里
我们用单调栈来维护每一个小矩形的左侧和右侧第一个比它低的矩形的位置。为什么要维护这个呢？根据木桶原理，每一个大矩形的高度是由其高度最小的矩形的高度决定的，所以我们要去记录第一个比当前矩形小的矩形的位置。
ps：别忘了初始化qwq……
附一下代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define pie 3.1415926

using namespace std;

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

int n,t,q,l[100005],r[100005],sta[100005],p;

struct build{
    int x,h;
}b[100005];

void init1(int k)
{
    if(p == 0)
    {
        sta[++p] = k;
        return ;
    }
    if(b[k].h >= b[sta[p]].h)
    {
        sta[++p] = k;
        return ;
    }
    while(b[sta[p]].h > b[k].h && p) 
    {
        l[sta[p]] = k;
        p --;
    }
    sta[++p] = k;
}

void init2(int k)
{
    if(p == 0)
    {
        sta[++p] = k;
        return ;
    }
    if(b[k].h >= b[sta[p]].h)
    {
        sta[++p] = k;
        return ;
    }
    while(b[sta[p]].h > b[k].h && p)
    {
        r[sta[p]] = k;
        p --;
    }
    sta[++p] = k;
}

ll ans;

int main()
{
    n = read();
    while(n != 0)
    {
        ans = 0;
        memset(b,0,sizeof(b));
        for(int i = 1; i <= n; i++)
        {
            b[i].h = read();
            b[i].x = i;
        }
        p = 0;
        for(int i = 1; i <= n + 1; i++) init1(i);
        p = 0;
        for(int i = n; i >= 0; i--) init2(i);
        for(int i = 1; i <= n; i++)
        {
            ans = max(ans,1LL * (l[i] - r[i] - 1) * b[i].h);
        }
        printf("%lld\n",ans);
        n = read();
    }
    return 0;
}