单调队列 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

习题