单调队列&单调栈归纳
单调队列
求长度为M的区间内的最大(小)值
单调队列的基本操作,也就是经典的滑动窗口问题。
求长度为M的区间内最大值和最小值的最大差值
两个单调队列,求出长度为M的区间最大最小值的数组,分别求最大最小值。
求边长为a的正方形内最大值和最小值的最大差值([HAOI2007]理想的正方形)
一个大体的思路是先分别求出以i,j为左上端点的边长为a的矩形中的最大值和最小值。那么该怎么做?,先用单调队列求出一个点右边a个单位的最大值,形成一个新矩阵,再求出新矩阵下边a个单位的最大值。然后最小值再求一边,最后统计答案。有的题有点变态,需要求,一个矩形中,一个A行B列矩阵权值和减去其中一个C行D列矩阵权值和的最大值。只要想到把C行D列矩阵缩成一个点,然后套本题的解法就行了。
求最大值和最小值差值小于D的区间的最小长度
问题显然具有单调性,单调队列右端点先扩展,直到满足差值小于D,左端点再尽量收缩。实现有一些代码技巧。
那么如果区间中的每个点有两个关键字a,b,问题改成求最大a值与最小b值的差值呢?
同时操作两个单调队列就行了。
求给定序列长度不超过M的最大连续字段和(P1714切蛋糕)
觉得有一定难度,实际上就是求max(sum[i]-sum[j])(i>=j,0<=i-j<m),所以就要用前缀和,然后直接两个单调队列分别求最大最小值不行,因为不知道i是否大于等于j,所以转化一下,就是求sum[i]-min(sum[j])(i>=j,0<=i-j<m),复杂度就多了个O(N),这样就可以解决这个问题了。
单调栈
其实单调栈就是左端点不移动的单调队列。
找到每一个a[i]右(左)边第一个比a[i]大(小)的数
单调栈的基本操作,正处理的数比栈顶的数大(小)时弹栈,给弹栈的数记录一下就行了。用这种方法也可以求出左边和右边最后一个比它大(小)的数。
矩形面积最大
一种题是规定矩形的一边一定,且都在x轴上,用单调栈求出一个矩形左边和右边最后一个长比它长的矩形。然后统计一下答案,这里用了贪心的思想,保证包含最优解,复杂度为O(N)。然后一种题是在平面内的,给出一些点是否合法,求一个包含点都为合法的矩形的最大面积。上一种题的扩展,把每一行都当做一次x轴都统计一下答案就行了。这种题型可以拓展到答案涉及到区间最小值且拥有单调性的一系列问题。
最新文章
- JS中实现数组和对象的深拷贝和浅拷贝
- 关于《加密与解密》的读后感----对dump脱壳的一点思考
- 【MVC 4】1.第一个 MVC 应用程序
- 百度翻译API
- bzoj3571: [Hnoi2014]画框 最小乘积匹配+最小乘积XX总结,
- VB------VS2012 IDE
- Debian6安装XP系统
- 提高你的Java代码质量吧:使用构造函数协助描述枚举项
- easyui验证扩展
- AVS、MPEG-2、H264标准文档
- JavaEE EL &; JSTL 学习笔记
- FFmpeg的HEVC解码器源代码简单分析:CTU解码(CTU Decode)部分-TU
- maven隐式依赖引起的包冲突
- Eclipse安装SVN插件(转载)
- Memcached的安装配置与测试
- easyui获取选中行上一行的数据
- shell编程基础(四): shell脚本语法之函数及调试
- Java监听器Listener使用详解
- lavarel 中间件
- 大牛的距离(笑cry)精简算法
热门文章
- 132.try throw catch介绍
- Ubuntu16.04+GTX 1080Ti+CUDA 8.0+cuDNN+Tesnorflow1.0深度学习服务器安装之路
- C语言学习小记
- [ZJOI2006]物流运输 最短路 动态规划
- luogu P2252 取石子游戏(威佐夫博弈)
- C指针思考-(1)
- 架构思想之CAP原理
- vjudge A - Beautiful numbers
- hdu5371Hotaru&;#39;s problem manacher算法
- ssh跳板登陆太麻烦,使用expect每次自动登录 利用expect 模拟键盘动作,在闲置时间之内模拟地给个键盘响应