单调队列
性质
单调队列和单调栈很像,就是一个维护了单调性的队列数据结构,可以是单调递增的,也可以是单调递减的。
模型
下图是一个单调递增的单调队列模型。
其中元素也是从小到大排列。
和单调栈的操作一样,如果加入一个满足单调性的元素,例如5,那么就直接加入。
那么如果加入一个元素3呢?我们维护单调性,需要把队列尾端把大于3的元素全部弹出,那么就需要用双端队列来实现了,当然操作和单调栈是一样的。
单调队列有许多作用:
比如可以求出一个数组内第一个大于等于一个数x的数
也可以通过维护单调性,解决一些区间内最小或最大的问题
总之单调队列的应用在根本上要视题目而定的灵活运用
本质上并不复杂
题目描述
现在有一堆数字共N个数字(N<=10^6),以及一个大小为k
的窗口。现在这个从左边开始向右滑动,每次滑动一个单
位,求出每次滑动后窗口中的最大值和最小值。
例如:
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
输入格式:
输入一共有两行,第一行为n,k。
第二行为n个数(<INT_MAX).
输出格式:
输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入样例#1:
8 3
1 3 -1 -3 5 3 6 7
输出样例#1:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
请用C++提交
#include#include #include #include #include #include #include #include #include #include #include #include #include