HDU 1506 Largest Rectangle in a Histogram

题意:

给出一个长度为n的序列,这些序列代表每个宽度为1的矩形的高,矩形是按顺序连在一起的,问最大相连面积(高为相连矩形的最小)。

思路:

对于每个最大连续的矩阵区间,如果它的边界有比这个区间最矮的矩形高的矩形,那么高的矩形肯定会被合并进去的。即找到每个节点的从左(从右)第一个比它小的节点, 这样就是当前节点能构成的最大连续矩形,用单调栈解决。

单调栈具体操作就是对于每个点 i ,如果栈顶元素大于等于 a[i] ,就把栈顶弹出,然后就能得到最左边(或右边)的区间端点下标(区间不包含该点),注意一下如果全部被弹出了,得到的边界下标就是0或者n+1。

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,a[N],l[N],r[N];
stack<ll>q1,q2;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++)
            cin>>a[i];
        while(!q1.empty())q1.pop();
        while(!q2.empty())q2.pop();
        for(ll i=1;i<=n;i++)
        {
            while(!q1.empty()&&a[q1.top()]>=a[i])q1.pop();
            if(q1.empty())l[i]=0;
            else l[i]=q1.top();
            q1.push(i);
        }
        for(ll i=n;i>=1;i--)
        {
            while(!q2.empty()&&a[q2.top()]>=a[i])q2.pop();
            if(q2.empty())r[i]=n+1;
            else r[i]=q2.top();
            q2.push(i);
        }
        ll mx=0;
        for(int i=1;i<=n;i++)
            mx=max(mx,(r[i]-l[i]-1)*a[i]);
        printf("%lld\n",mx);
    }
    return 0;
}