首页 > 代码库 > HDU 1506 && POJ 2559 Largest Rectangle in a Histogram (单调队列)
HDU 1506 && POJ 2559 Largest Rectangle in a Histogram (单调队列)
题目链接:POJ 2559 Largest Rectangle in a Histogram
题目链接:HDU 1506 Largest Rectangle in a Histogram
题意:给出一串序列表示对应矩形的高度,求整个图中最大的矩形区域。
2, 1, 4, 5, 1, 3, 3
如图所示:
思路:每个矩形向左向右最大能扩张到的长度乘上他的高度,求最大值就是答案。
用单调队列维护序列递减,出队列的元素即是“极值”点
注意:要用int64.
AC代码:
#include<stdio.h> #include<string.h> #define ll __int64 struct node { ll l,r; ll sum; }; struct node que[100010]; ll h[100010]; ll pre[100010],next[100010];//pre记录hi向左递减最远位置,next记录hi向右递减最远位置, int main() { ll n,i; ll head,tail; while(scanf("%I64d",&n)!=EOF,n) { memset(que,0,sizeof que); for(i=1;i<=n;i++) { scanf("%I64d",&h[i]); pre[i]=n; next[i]=1; } head=1,tail=0; for(i=1;i<=n;i++) { while(head<=tail && h[i]<que[tail].sum)//维护单调递减队列 { pre[que[tail].l]=i-1;//出队列的元素是他扩张右边最远位置 tail--;//弹出元素 } que[++tail].sum=h[i];//入队列 que[tail].l=i;//记录位置。 } head=1,tail=0; for(i=n;i>=1;i--) { while(head<=tail && h[i]<que[tail].sum) { next[que[tail].r]=i+1;//出队列的元素是他扩张左边最远位置 tail--; } que[++tail].sum=h[i]; que[tail].r=i; } ll ans=0,temp; for(i=1;i<=n;i++) { temp=(pre[i]-next[i]+1)*h[i]; if(temp>ans) ans=temp; } printf("%I64d\n",ans); } return 0; }
HDU 1506 && POJ 2559 Largest Rectangle in a Histogram (单调队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。