单调栈&单调队列学习笔记!
ummm,,,都是单调系列就都一起学了算了思想应该都差不多呢qwq
其实感觉这俩没有什么可说的鸭QAQ就是维护一个单调的东西,区别在于单调栈是一段进一段出然后单调队列是一段进另一段出?没了
好趴辣重点港下适用范围qwq
1)直方图最大矩形(单调栈[X]
rt,给个直方图求最大矩形面积 例
换一个表达,给一个序列,求一个子序列使得这个子序列中的min*序列长度max,一样的意思嗷注意一下? 例
昂首先想如果高度单调递增怎么搞,显然是贪心地把每个高度算出它延伸到右边界的面积取max
那如果右边这个比左边矮呢
显然左边高的那部分就没有贡献了,于是可以被弹掉,变成和右边的高度相等的矩形
从这里可以得出维护一个高度单调增的单调栈就欧克辣,然后每次弹出的时候就是这个高度能延伸到的最边上于是更新一波就完成辽qwq
2)最大子序和(单调队列[X]
给一个序列,找出长度<=m的连续子序列使得和max 例
昂首先区间和显然是用前缀和+做差嘛
然后考虑确定了右端点r,那找的就是minSi且i∈[r-m,r-1]
然后显然的是如果有一个si的右边有小于它的它肯定无法起贡献了,可以弹掉
另外还有一个就是当l已经不在[r-m,r-1]范围内的时候也可以一直弹弹弹
3)最大数(单调栈[X]
给一个序列,找出最后L个数中最小的数 例
昂和前面那个的思想差不多,而且我写了题解来着?不想写了qwq就放个链接算了qwq
4)不会总结了QAQ(单调栈[X]
给一个序列,求某个数的左边比它大的数之间有几个数 例
ummm就是开个递减的单调队列,弹的时候记个size就好辣!
5)不会总结名字QAQ(单调栈[X]
给一个序列,求一个子序列使得这个子序列中的min*序列之和max 例
说实话一开始看到这题没想到QAQ所以写个题解算了QAQ
6)区间内最大最小值(单调队列+单调栈[X]
给一个序列,一个长度,求每个点为起点的给定长度区间内的min和max 例
挺经典的还?其实就滑动窗口qwq应该是最模板的qwq不说了实在太简单QAQ
大概就这几类题目?先这样,想到了再补充!over!
最新文章
- 完成C++不能做到的事 - Visitor模式
- crawler: 爬虫的基本结构
- 一个Struts2的实例
- 如何确定某个counter对应的rrd文件
- MySql解决插入中文乱码问题
- SqlServer中把结果集放到到临时表的方法
- 将 Sublime 3 打造成 Python/Django IDE
- iOS推送通知流程
- python_Opencv_图像的基础操作
- RadioButton、CheckBox与ToggleButton
- angularJS看MVVM
- 错排-HDU 2049 递推的应用
- yarn的调度器
- HDU 2544 最短路(dijkstra+邻接矩阵)
- C# winform DatagridView 的简单操作
- [ffmpeg] 多输入滤波同步方式（framesync）
- Java提高班（二）深入理解线程池ThreadPool
- 业务开发（一）—— MySQL
- redis启动出错Creating Server TCP listening socket 127.0.0.1:6379: bind: No error(转)
- React项目中实现右键自定义菜单