概述

单调队列是一种广泛应用的数据结构，它能够动态地维护定长序列中的最值，可以应用于求最值与优化DP转移等方面。本文章将讲述单调队列的原理、实现及应用。
除本文提到的例子以外，更多示例可以参见DP的花式优化方法 | KSkun’s Blog。

原理

单调队列实质上是一类双端队列（deque），在加入一个元素时，我们通过一定操作维护队列的单调性。该队列特征的操作便是“后移一位”。顾名思义，后移一位就是指队列维护的区间往后移一位。这个操作中要做的事情是弹出队首与加入队尾。

加入队尾

为了保证这个队列中元素的单调性，对于加入的元素，我们可能要删除一些队尾的元素。以不下降的单调队列为例（下同），插入时要弹出所有比要插入元素大的队尾元素，直到队尾元素不再比其大再插入。此时插入元素时要记下插入元素在原序列中的位置，这个信息将会对弹出队首时发挥作用。

弹出队首

对于插入的元素，我们检查它与队首元素的位置之差，当这个差大于队列定长时说明队首元素已在区间之外，应当弹出。

例子

下面来看一组例子，以加深理解。我们维护一个序列中，定长为3的递增区间。这个序列给定为1 3 2 6 4 9 0 11。
先向队列中插入1。此时队列为1(1)。
由于长度未达到3，直接再插入3。此时队列为1(1) 3(2)。
插入2时，发现队尾存在比2大的3，弹出3。此时队列为1(1) 2(3)。队列长已满足3。
再插入6，发现序列头元素已经在区间外，弹出1。此时队列为2(3) 6(4)。
接下来的步骤不再描述。

实现

假设我们在实现一种维护长为k的递增区间，且序列a总长为n。
注：以下代码未测试，仅供参考，如有错误欢迎在评论指正。

STL deque

que为双端队列。队列中元素为结构体，存有值(v)和位置(pos)。

for(int i = 1; i <= n; i++) {
    while(que.back().v >= a[i]) que.pop_back();
    que.push_back(Node(a[i], i));
    if(que.front().pos == i - n) que.pop_front();
}

手写队列

l、r为队首、队尾指针，pos为位置。

for(int i = 1; i <= n; i++) {
    while(que[r - 1] >= a[i]) r--;
    que[r] = a[i];
    pos[r] = i;
    r++;
    if(pos[l] == i - n) l++;
}

应用

维护定长区间内最值：[HAOI2007]理想的正方形

题目描述

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入输出格式

输入格式：
第一行为3个整数，分别表示a,b,n的值
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出格式：
仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例

输入样例#1：

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

输出样例#1：

1

说明

问题规模

1. 矩阵中的所有数都不超过1,000,000,000
2. 20%的数据2 \leq a,b \leq 100,n \leq 10
3. 100%的数据2 \leq a,b \leq 1000,n \leq a,n \leq b,n \leq 100

题解

在本题中，单调队列发挥了与ST表相似的功能，即维护定长区间最值。我们考虑这个正方形是由n行长为n的区间构成的。因此可以对原矩阵中每一行的每一个长为n的区间分别求最大最小值，记录下来，再在记录的数组中对每列长为n的区间分别求最大最小值。其最小差即为答案。这种做法相当于先将行上的区间抽象成一个点，这样一个正方形相当于列上的一个区间。

代码

// Code by KSkun, 2018/1 
#include <cstdio>
#include <algorithm>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0, neg = 1;
        while(*s < '0' || *s > '9') if(*(s++) == '-') neg = -1;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res * neg;
    }
} ip;

#define read ip.read

int a, b, n, mat[1005][1005], pos[1005], mx[1005][1005], mn[1005][1005], 
    que[1005], mmx[1005], mmn[1005], l, r, ans = 1e9;

int main() {
    a = read();
    b = read();
    n = read();
    for(int i = 1; i <= a; i++) {
        for(int j = 1; j <= b; j++) {
            mat[i][j] = read();
        }
    }
    for(int i = 1; i <= a; i++) {
        l = r = 1;
        for(int j = 1; j <= b; j++) {
            while(l < r && que[r - 1] <= mat[i][j]) r--;
            que[r] = mat[i][j];
            pos[r] = j;
            r++;
            if(pos[l] == j - n) l++;
            if(j >= n) mx[i][j] = que[l];
        }
        l = r = 1;
        for(int j = 1; j <= b; j++) {
            while(l < r && que[r - 1] >= mat[i][j]) r--;
            que[r] = mat[i][j];
            pos[r] = j;
            r++;
            if(pos[l] == j - n) l++;
            if(j >= n) mn[i][j] = que[l];
        }
    }
    for(int i = n; i <= b; i++) {
        l = r = 1;
        for(int j = 1; j <= a; j++) {
            while(l < r && que[r - 1] <= mx[j][i]) r--;
            que[r] = mx[j][i];
            pos[r] = j;
            r++;
            if(pos[l] == j - n) l++;
            if(j >= n) mmx[j] = que[l];
        }
        l = r = 1;
        for(int j = 1; j <= a; j++) {
            while(l < r && que[r - 1] >= mn[j][i]) r--;
            que[r] = mn[j][i];
            pos[r] = j;
            r++;
            if(pos[l] == j - n) l++;
            if(j >= n) mmn[j] = que[l];
        }
        for(int j = n; j <= a; j++) {
            ans = std::min(ans, mmx[j] - mmn[j]);
        }
    }
    printf("%d", ans);
    return 0;
}

优化DP转移的复杂度：POJ2373 Dividing the Path

题目大意

有一段[0, L]的大草场，现在在其中某些不要求为整点的位置安装洒水器使得每个点都恰好被1个洒水器的洒水范围覆盖。洒水器的范围可以调节，范围半径为[A, B]。草场中有一些区间必须整个被恰好1个洒水器所覆盖。
数据范围：1 \leq L \leq 10^6, 1 \leq A \leq B \leq 1000, 1 \leq N \leq 1000

题解

考虑DP解决这个问题。
用dp[i]表示[0, i]区间被完全覆盖所需的最少洒水器数量。可以发现，如果i是一个奇数，那么不存在一种覆盖的方案，因为洒水器覆盖的区间长度[2A, 2B]，必须为偶数。转移方程如下。
dp[i] = \min_{j=i-2B}^{i-2A} dp[j] + 1
上述方程中，除要求j的取值外还要求j处存在合法方案以及j不是题目描述的特殊区间。
关于特殊区间的处理，直接令区间内的位置dp值为INF。这样它是不会被转移的，也就是说，不存在一种方案会使得这个区间内的位置成为两个洒水器范围的分界点。
然而我们发现暴力遍历转移的复杂度是O(n \cdot (2B - 2A))的，对于数据范围还是不够，考虑用单调队列优化中间这个找最小值的过程。
找最小值就是一个长度为2B-2A的区间在序列上滑动的过程，自然可以用单调队列维护这个序列中的最小值，至此，我们可以将算法优化至O(n)。

代码

吐槽：写的时候符号写反了WA了一次才过233

// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <deque>
#include <algorithm> 

const int INF = 0x3f3f3f3f;

struct Node {
    int v, pos;
    Node(int v, int pos): v(v), pos(pos) {} 
};

std::deque<Node> que;
int n, l, a, b, xt, yt, dp[1000005], tag[1000005]; 

int main() {
    memset(dp, 0x3f, sizeof dp);
    scanf("%d%d%d%d", &n, &l, &a, &b);
    if(l & 1) { // l为奇数时无法被完全覆盖 
        printf("-1");
        return 0;
    }
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &xt, &yt);
        tag[xt + 1] += 1;
        tag[yt] -= 1; 
    }
    for(int i = 1; i <= l; i++) {
        tag[i] += tag[i - 1];
    }
    dp[0] = 0;
    for(int i = 2; i <= l; i += 2) {
        if(i - 2 * a >= 0 && !tag[i - 2 * a] && !((i - 2 * a) & 1)) {
            while(!que.empty() && que.back().v >= dp[i - 2 * a]) {
                que.pop_back();
            }
            que.push_back(Node(dp[i - 2 * a], i - 2 * a));
        }
        while(!que.empty() && que.front().pos < i - 2 * b) que.pop_front();
        if(!tag[i] && !que.empty()) {
            dp[i] = std::min(dp[i], que.front().v + 1);
        }
    }
    if(dp[l] >= INF) {
        printf("-1");
    } else {
        printf("%d", dp[l]);
    }
    return 0;
}