频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU OJ 1506 Largest Rectangle in a Histogram 和 NYOJ 258 最大长方形 [单调队列]
2012-07-12 16:00:15           
收藏   我要投稿
思路:单调队列,开 两个数组 stack [ ] 和 len  [ ]  stack [ ] 存 输入的 长 len [  ] 存宽。stack 里面 按 单增 存,遇到 比 stack [ top ] 小的 数据 就要 讲 顶部元素删除,直到 删后 顶部可以存 为止,在删之前 要 看是否 可以更新 ans ((l+len[ top ])*stack[ top ] 与 当前 ans 取最大值给 ans),记下 此时 len [ top ] 的值,给  l (l+=len[ top ]),新进入的 len 值 即为 l +1 , 具体看代码理解。
AC代码:
[cpp] 
 /*此代码为 nyoj ac 代码,若在 hdu oj 要讲 long long 改为 __int64(对应输出格式也要改下),hdu oj 不支持 long long*/ 
#include<stdio.h> 
#include<string.h> 
#define max(a,b) a>b?a:b  
int stack[100010],len[100010]; 
int main() 

    int a,b,n,h; 
    while(scanf("%d",&n)&&n) 
    { 
        long long top=-1,ans=0; 
        for(a=0;a<=n;a++) 
        { 
            if(a<n) 
                scanf("%d",&h); 
            else 
                h=-1; 
            if(top<0||stack[top]<h) 
            { 
                stack[++top]=h; 
                len[top]=1; 
            } 
            else 
            { 
                int l=0; 
                while(stack[top]>=h&&top>=0) 
                { 
                    ans= max(ans,(long long)(len[top]+l)*stack[top]); 
                    l+= len[top--]; 
                } 
                if(h>0) 
                { 
                    stack[++top]=h; 
                    len[top]=1+l; 
                } 
            } 
        } 
        printf("%lld\n",ans); 
    } 
}         
作者:PIAOYI0208
点击复制链接 与好友分享!回本站首页
相关TAG标签 长方形 队列
上一篇:HDU 1712 ACboy needs your help 多组背包
下一篇:编程之美--数字之魅
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站