题解 POJ 2559【Largest Rectangle in a Histogram】(单调栈)
2024-09-07 16:02:13
题目链接:http://poj.org/problem?id=2559
思路:单调栈
什么是单调栈?
单调栈,顾名思义,就是单调的栈,也就是占中存的东西永远是单调(也就是递增或递减)的
如何实现一个单调栈呢?过程很简单。假设栈中已有了若干单调递增的元素,此时我们又有了一个元素,如果这个元素比栈顶元素大,则直接入栈;反之,不断弹出当前元素,直到栈顶元素比之前小为止。(这里实现的是一个单调递增栈,递减栈和递增栈的过程一样)
为什么这道题可以用单调栈?
假设矩形的高度从左到右递增,那么答案是多少?显而易见,我们可以尝试以每个矩形的高度作为最终矩形的高度,并把宽度延伸到右边界,得到一个矩形,在所有这样的矩形面积中取最大值就是答案。
然而矩形的高度不一定是递增的,如果新加入的矩形比上一个小,那么之前这些矩形的高度对于后面的计算就没用了。
具体实现的方法简单说就是将之前比这高的矩形弹出栈知道遇到比新矩形低的矩形,同时累计他们的宽度之和,乘以这个更矮矩形的高度来更新答案。最后再按这个方法把所有矩形弹出去来更新答案。
AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
#define N 100005
ll s[N],w[N],a[N];//s为栈,w为宽度,a为高度
int top=0;
void init()//初始化
{
memset(s,0,sizeof(s));
memset(w,0,sizeof(w));
memset(a,0,sizeof(a));
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n!=0)
{
init();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll ans=0;
a[n+1]=top=0;
for(int i=1;i<=n+1;i++)
{
if(a[i]>=s[top])//单调队列
{
s[++top]=a[i];
w[top]=1;
}
else
{
ll tmp=0;
while(a[i]<s[top])
{
tmp+=w[top];
ans=max(ans,tmp*s[top]);//更新最大值
top--;
}
s[++top]=a[i];
w[top]=tmp+1;
}
}
printf("%lld\n",ans);
}
return 0;
}
参考资料
《算法竞赛进阶指南》 河南电子音像出版社 李煜东·著
最新文章
- 只用@property定义一个属性speed,子类不能直接用_speed,需要在interface的成员变量列表里写上_speed
- FZU-2075 Substring(后缀数组)
- 写在分类之首-----to do list!
- equals
- WinForm多线程学习文档
- count有关
- C语言中的const
- css的优先级以及!important的使用
- 触发器(基本的SR触发器、同步触发器、D触发器)
- npm install fetchmatedata慢的解决办法
- colinux
- JVM笔记6-垃圾回收概述
- window下编译jcef
- Unity 2018.2.8 旧版本安装包和破解软件
- 牛客第六场 J.Heritage of skywalkert(On求前k大)
- 二十一、curator recipes之TreeCache
- Windows Server 2008 R2下将JBoss安装成windows系统服务
- TPL中限制进程数量
- PyCharm永久激活
- HttpWebRequest和HttpWebResponse的应用
热门文章
- C# HttpClient Post 参数同时上传文件 上传图片 调用接口
- Windows平台部署 Asp.Net Core 3.1.0,将 ASP.NET Core 应用发布到 IIS ,使用 IIS 在 Windows 上托管 ASP.NET Core
- 【转】Pandas学习笔记(一)基本介绍
- windows server 2008 安装MySQL 8.0 遇到报错 1055 - Expression #1 of ORDER BY clause is not in GROUP BY
- Django常用自段和参数
- 201871010131-张兴盼《面向对象程序设计(java)》第二周学习总结
- 火车头data下任务文件夹的SpiderResult.db3文件用什么软件打开
- 【myBatis】Error evaluating expression ‘’. Return value () was not iterable.
- IIS添加MIME类型.woff/.svg/.woff2/.eot/.otf.ttf
- 请简述get请求和post请求的区别