单调队列 Monotonic Queue

例题POJ 2823 Sliding Window，长度为\(n\)的数组，编程输出每\(k\)个连续的数中的最大和最小值。

笨办法每次都取\(k\)个数来比较，所以复杂度是\(O(nk)\)，单调队列方法尽量复用之间做的比较结果，可以做到一遍扫描完成，复杂度O(n)。

单调队列算法不变量如下：以找最小值为例，我们维护当前\(k\)个字符窗口中的一个单调增的数字的序列（队列），保证队列头部（最小）的数字是窗口中的最小值。

依次向右扫描新的数字，做两个操作就可以保证这个不变量：

如果扫描时碰到的数字比队列尾部数字大，则加入队列，否则将队尾数字依次删除。
如果队列头部数字不在窗口中，则将头部数字删除。

这样每个数字最多进出队列一次，队列用\(n\)长度的下标数组维护，算法复杂度\(O(n)\)。

参考代码

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

单调队列 Monotonic Queue

习题