单调队列是一种内部元素具有单调性的队列，可以解决求“区间内最值”的问题。
例：P1886 滑动窗口 /【模板】单调队列
分析：暴力枚举的方式是进行 \(n-k\) 次循环，每次查找长度为 \(k\) 区间的最值，这样的算法时间复杂度是 \(O(nk)\) 的，无法通过这个题目。
以下分析以最大值为例，最小值同理。可以建立一个队列来维护这些数据，队首在左，队尾在右。首先队列为空，将元素加入到队列中。如果接下来的元素比队尾元素更大，那么将队尾元素出队，直到这个元素不大于队尾元素为止。当处理到的数据下标大于等于 \(k\)，说明已经处理完了 \(k\) 个数字，可以查询这个区间的最大值了。这里的最大值就是队首元素。
在每次新加入元素之前，先要检查队首元素是否过期（不再处于需要统计的区间中）：如果队首元素的下标小于等于 \(i-k\)，说明队首元素过期了，此时队首元素就需要出队。
例如数据依次为[3,9,1,12,5,8,10,6]，而k=4，维护过程如下：
这个队列不仅可以从队尾入队、队首出队，还可以从队尾出队（想象一个队伍在排队，排在最后的人发现后面要加入队伍的人惹不起，主动放弃了排队）。使用这种队列，保障队列内的元素具有单调性，这种队列被称为单调队列。
#include <cstdio>
#include <deque>
using namespace std;
const int N = 1000005;
int a[N];
int main()
{
int n, k; scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
deque<int> dq;
for (int i = 1; i <= n; i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k) printf("%d%c", a[dq.front()], i == n ? '\n' : ' ');
}
dq.clear();
for (int i = 1; i <= n; i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k) printf("%d%c", a[dq.front()], i == n ? '\n' : ' ');
}
return 0;
}
因为要知道队首元素是否过期，单调队列里面存储的实际上是下标而不是数据本身。
例：P2216 [HAOI2007] 理想的正方形
有一个 \(a \times b\) 的整数组成的矩阵，现请你从中找出一个 \(n \times n\) 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
保证 \(2 \le a,b \le 1000, n \le a, n \le b, n \le 100\)，矩阵的元素均为不超过 \(10^9\) 的非负整数。
分析：暴力枚举的方式是枚举所有符合要求的小正方形，每次在正方形中查找最小最大值并统计，这样时间复杂度是 \(O(n^2 (a-n+1)(b-n+1))\)，不能通过这个题目。
如何求出一个正方形矩阵的最大值呢？可以将这个正方形的每一行数字求最大值，然后再求每一行最大值中的最大值，剩下的一个值就是这个正方形矩阵的最大值。
以样例为例，首先处理每一行，找出一行中每一个长度为 \(2\) 的区间的最大值；然后处理每一列，找到一列中每一个长度为 \(2\) 的区间的最大值。最后得到的矩阵中的一个元素就对应着一个 \(2 \times 2\) 的正方形的最大值。使用相同的方式求得每个 \(2 \times 2\) 正方形的最小值，然后遍历这两个矩阵，计算这两个数的极差并统计即得到答案。
可以使用单调队列来求指定区间的最值。
#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;
const int N = 1005;
const int INF = 1000000000;
int mat[N][N], r1[N][N], r2[N][N], mn[N][N], mx[N][N];
int main()
{
int a, b, n;
scanf("%d%d%d", &a, &b, &n);
for (int i = 1; i <= a; i++)
for (int j = 1; j <= b; j++)
scanf("%d", &mat[i][j]);
deque<int> qmin, qmax;
for (int i = 1; i <= a; i++) {
// 求每行区间最大、最小值
qmin.clear(); qmax.clear();
for (int j = 1; j < n; j++) {
while (!qmin.empty() && mat[i][qmin.back()] >= mat[i][j])
qmin.pop_back();
qmin.push_back(j);
while (!qmax.empty() && mat[i][qmax.back()] <= mat[i][j])
qmax.pop_back();
qmax.push_back(j);
}
for (int j = 1; j <= b - n + 1; j++) {
while (!qmin.empty() && qmin.front() < j)
qmin.pop_front();
while (!qmin.empty() && mat[i][qmin.back()] >= mat[i][j + n - 1])
qmin.pop_back();
qmin.push_back(j + n - 1);
r1[i][j] = mat[i][qmin.front()];
while (!qmax.empty() && qmax.front() < j)
qmax.pop_front();
while (!qmax.empty() && mat[i][qmax.back()] <= mat[i][j + n - 1])
qmax.pop_back();
qmax.push_back(j + n - 1);
r2[i][j] = mat[i][qmax.front()];
}
}
for (int i = 1; i <= b - n + 1; i++) {
// 在刚刚得到的新矩阵的基础上，求每列区间最大、最小值
qmin.clear(); qmax.clear();
for (int j = 1; j < n; j++) {
while (!qmin.empty() && r1[qmin.back()][i] >= r1[j][i])
qmin.pop_back();
qmin.push_back(j);
while (!qmax.empty() && r2[qmax.back()][i] <= r2[j][i])
qmax.pop_back();
qmax.push_back(j);
}
for (int j = 1; j <= a - n + 1; j++) {
while (!qmin.empty() && qmin.front() < j)
qmin.pop_front();
while (!qmin.empty() && r1[qmin.back()][i] >= r1[j + n - 1][i])
qmin.pop_back();
qmin.push_back(j + n - 1);
mn[j][i] = r1[qmin.front()][i];
while (!qmax.empty() && qmax.front() < j)
qmax.pop_front();
while (!qmax.empty() && r2[qmax.back()][i] <= r2[j + n - 1][i])
qmax.pop_back();
qmax.push_back(j + n - 1);
mx[j][i] = r2[qmax.front()][i];
}
}
int ans = INF;
for (int i = 1; i <= a - n + 1; i++)
for (int j = 1; j <= b - n + 1; j++)
ans = min(ans, mx[i][j] - mn[i][j]);
printf("%d\n", ans);
return 0;
}