HDU Largest Rectangle in a Histogram —— 单调栈

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题意

给你n个宽为1高为a[i]的矩形在其中划分出一个被它们包含的矩形问你最大矩形面积是多少。

题解

    首先就是需要使用__int64作为输入输出我用ll一直wa。
    那么可以注意到最终矩形的高度是可以确定的一定是某个宽度为1的矩形的高度。于是我们就可以枚举每个矩形看看如果是它作为最终答案的高的话最大宽度是多少。
    这道题就变成了枚举每个点求左边和右边离它最近的高度低于它的点下标。然后下标相减再乘上高度就是最终的答案了。
    求一个点左边的比它小的点的坐标我们就可以用递增的单调栈。

#include<iostream>
#include<stdio.h>
using namespace std;
#define ll long long
const int N=1e5+5;
__int64 a[N],st[N],top,lef[N];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        top=0;
        if(n==0)break;
        __int64 ans=0;
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
            while(top && a[st[top]]>=a[i])top--;
            lef[i]=top?st[top]+1:1;
            st[++top]=i;
        }
        top=0;
        for(int i=n;i;i--){
            while(top && a[st[top]]>=a[i])top--;
            __int64 rig=top?st[top]-1:n;
            ans=max(ans,(rig-lef[i]+1)*a[i]);
            st[++top]=i;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}