数据结构 — 单调队列

顾名思义,单调队列的重点分为 “单调” 和 “队列”

“单调” 指的是元素的的 “规律”——递增(或递减)

“队列” 指的是元素只能从队头和队尾进行操作

  • 单调递增队列:保证队列头元素一定是当前队列的最小值,用于维护区间的最小值。
  • 单调递减队列:保证队列头元素一定是当前队列的最大值,用于维护区间的最大值。

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;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注