POJ 2559 Largest Rectangle in a Histogram(单调栈) && 单调栈
2024-10-08 13:40:05
嗯...
题目链接:http://poj.org/problem?id=2559
一、单调栈:
1.性质:
单调栈是一种特殊的栈,特殊之处在于栈内的元素都保持一个单调性,可能为单调递增,也可能为单调递减。
2.模样:
这是一个单调递增的栈,如果我们插入的元素大于栈顶元素,则直接入栈;
如果我们插入的元素小于栈顶,则需要把栈内所有大于它的元素暂时出栈,将这个元素入栈后,再将暂时出栈的元素入栈,维护单调性。
二、模板:
这道题是单调栈的一道模板题:
先思考一个问题,如果题目中的矩形的高度都是单调递增的,如何得到最优解?
显然有一个贪心的策略,就是以每一个矩形的高度作为最终大矩形的高度,看最宽能是多少,然后统计最优解。
但如果进来的下一矩形比上一个低,它其实相当于限制了之前矩形的高度,那么之前矩形比这个矩形高出的高度在以后的统计中就没有丝毫用处了。
这样,我们实际上就得到了单调栈的模型,只需要维护一个单调栈,在维护单调性的弹出操作时统计宽度,更新答案即可在O(n)实际内得到最优解。
并且我们假设h[n+1]的位置有一个高度为0的矩形,最后将它加入单调栈时他会将所有矩形都弹出,那么答案也就完成最后的更新了。
AC代码:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std; int n, h[], w[], s[], top = ;
//h --> height w --> width s --> stack
inline bool input(){
scanf("%d", &n);
if(!n) return false;
for(int i = ; i <= n; i++)
scanf("%d", &h[i]);
h[n + ] = ;//最后用来清空栈
return true;
} inline long long work(){
long long ans = ;
for(int i = ; i <= n + ; i++){
if(h[i] > s[top]){
s[++top] = h[i];
w[top] = ;//宽度为1
}//满足单调
else{
int widthsum = ;//宽度和
while(s[top] > h[i]){
widthsum += w[top];
ans = max(ans, (long long) widthsum * s[top]);//注意高是s[top]
top--;
}
s[++top] = h[i];//此时s[top]已经小于h[i],满足单调
w[top] = widthsum + ;//合并
}
}
return ans;
} int main(){
while(input()){
printf("%lld\n", work());
top = ;
memset(s, , sizeof(s));
memset(h, , sizeof(h));
memset(w, , sizeof(w));
}
return ;
}
AC代码
最新文章
- Qml 写的弹出层控件
- php套件 wampserver 常见问题
- DirectX中的纹理及其创建
- DOM中事件绑定补充方法
- 数学之美 zt
- java返回参数中几种常见的方法
- OC - 21.CALayer核心要点及实例解析
- JSP的学习(8)——JSP标签
- VSTO学习笔记(十四)Excel数据透视表与PowerPivot
- SDL2源码分析5:更新纹理(SDL_UpdateTexture())
- 学会用git真的很重要
- spring boot - 整合jpa
- 在项目中迁移MS SQLServer到Mysql数据库,实现MySQL数据库的快速整合
- ConcurrentHashMap代码解析
- Java内存泄露监控工具:JVM监控工具介绍
- 20155201 网络攻防技术 实验九 Web安全基础
- U深度U盘安装win7系统教程
- python数字转换为字符串的两种方式
- RabbitMQ备份交换器
- 【洛谷P2016】战略游戏
热门文章
- TCL create list from file
- td标签内容:换行和不换行设置
- JS生成简单随机答案选择器,小抽奖器
- python正则匹配次数,贪婪和非贪婪
- 【安卓逆向】反编译ELF的另类技巧
- 【想见你】剧情解析byZlc
- 结构体sizeof()问题与字节对齐
- http://localhost:8080/sockjs-node/info?t=1556418283950 net:: ERR_CONNECTION_REFUSED(亲测有效~!)
- JS高级---构造函数,实例对象和原型对象,三者关系
- 【代码学习】PYTHON 深拷贝和浅拷贝