首页 > 其他 > 详细

《Largest Rectangle in a Histogram》

时间:2020-08-02 18:10:30      阅读:18      评论:0      收藏:0      [点我收藏+]

标签:元素   const   mod   一个   splay   else   

非常好的一道单调栈的题。

首先说一下单调栈,它维护的是一个单调的序列。

如果维护递增序列,那么栈顶大于当前值时,就pop栈顶,这样之后可以发现,栈顶的元素是左边最近的小于当前值的元素。

那么对于这道题,有一个很巧妙的转化方法:合并矩形

图片详解可见:https://blog.csdn.net/qq_19829595/article/details/96019508

考虑当前的栈中序列为

1 2 3 4 5 6.

那么合并矩形时:

sum = 6*1.

sum = 5*2

sum = 4*3

sum = 3*4

sum = 2*5

sum = 1*6

最后合并为 h = 1,w = 6.

可以发现,我们这样是在计算以栈顶位置结尾的能组成的最大矩形。

避免一直递增最后没有比较的情况发生,我们让h[n+1] = 0,保证了最后肯定会计算。

注意的是,如果ans = -INF,那么所以高度都为0的情况时,依旧不会算,这时可以让h[n+1] = -1。

或者一开始ans = 0.

技术分享图片
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<LL,int> pii;
const int N = 1e5+5;
const int M = 1e6+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
inline LL read()
{
    LL x = 0,f = 1;char c = getchar();
    while(c < 0 || c > 9){if(c == -) f = -1;c = getchar();}
    while(c >= 0 && c <= 9){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
LL S[N],w[N],h[N];
int main() 
{
    int n;
    while(n = read(),n != 0)
    {
        for(int i = 1;i <= n;++i) h[i] = read();
        int top = 0;
        LL ans = 0;
        h[n+1] = 0;
        for(int i = 1;i <= n+1;++i)
        {
            if(h[i] > S[top])
            {
                S[++top] = h[i];
                w[top] = 1;
            }
            else
            {
                LL width = 0;
                while(top != 0 && S[top] > h[i])
                {
                    width += w[top];
                    ans = max(ans,width*S[top]);
                    top--;
                } 
                S[++top] = h[i];
                w[top] = width+1;
            }
        }
        printf("%lld\n",ans);
    }
    system("pause");
    return 0;
}
View Code

 

《Largest Rectangle in a Histogram》

标签:元素   const   mod   一个   splay   else   

原文:https://www.cnblogs.com/zwjzwj/p/13418953.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号