顾名思义,单调队列的重点分为 “单调” 和 “队列”
“单调” 指的是元素的的 “规律”——递增(或递减)
“队列” 指的是元素只能从队头和队尾进行操作
- 单调递增队列:保证队列头元素一定是当前队列的最小值,用于维护区间的最小值。
- 单调递减队列:保证队列头元素一定是当前队列的最大值,用于维护区间的最大值。
1、对于单调递增队列,对于一个元素如果它大于等于队尾元素, 那么直接把元素进队, 如果这个元素小于队尾元素,则将队尾元素出队列,直到满足这个元素大于等于队尾元素。
2、对于单调递减队列,对于一个元素如果它小于等于队尾元素, 那么直接把元素进队, 如果这个元素大于队尾元素,则将队尾元素出队列,直到满足这个元素小于等于队尾元素。
3、判断队头元素是否在待求解的区间之内,如果不在,就将其删除。(这个很好理解呀,因为单调队列的队头元素就是待求解区间的极值)
4、经过上面两个操作,取出 队列的头元素 ,就是 当前区间的极值 。
可以发现队列中的元素都是单调递减的(不然也就不叫单调递减队列啦),同时既有入队列的操作、也有出队列的操作。
实现单调队列,主要分为三个部分:
- 去尾操作 :队尾元素出队列。当队列有新元素待入队,需要从队尾开始,删除影响队列单调性的元素,维护队列的单调性。(删除一个队尾元素后,就重新判断新的队尾元素)
去尾操作结束后,将该新元素入队列。
- 删头操作 :队头元素出队列。判断队头元素是否在待求解的区间之内,如果不在,就将其删除。(这个很好理解呀,因为单调队列的队头元素就是待求解区间的极值)
- 取解操作 :经过上面两个操作,取出 队列的头元素 ,就是 当前区间的极值 。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define maxn 1000100
using namespace std;
int q[maxn], a[maxn];
int n, k;
void getmin() { // 得到这个队列里的最小值,直接找到最后的就行了
int head = 0, tail = 0;
for (int i = 1; i < k; i++) {
while (head <= tail && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
}
for (int i = k; i <= n; i++) {
while (head <= tail && a[q[tail]] >= a[i]) tail--;
q[++tail] = i;
while (q[head] <= i - k) head++;
printf("%d ", a[q[head]]);
}
}
void getmax() { // 和上面同理
int head = 0, tail = 0;
for (int i = 1; i < k; i++) {
while (head <= tail && a[q[tail]] <= a[i]) tail--;
q[++tail] = i;
}
for (int i = k; i <= n; i++) {
while (head <= tail && a[q[tail]] <= a[i]) tail--;
q[++tail] = i;
while (q[head] <= i - k) head++;
printf("%d ", a[q[head]]);
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
getmin();
printf("\n");
getmax();
printf("\n");
return 0;
}