简单的问题引入
例题：CH1201
输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。
以前写的题解：CH1201:最大子序和题解
首先思考暴力：枚举端点和不大于\(m\)的长度，前缀和搞一搞就好，时间复杂度为\(O(n^2)\)，肯定超时。我们可以考虑优化这个算法。
单调队列
对于上面的问题，我们可以思考：我们肯定忽略了额外的信息，换句话说我们在运算过程中肯定忽略掉了一些可以进行优化的信息。考虑将可能的答案集设为\(S\)。我们只想要能使答案变大的决策，且这个决策点的距离不能超过\(m\)，但我们又不想失去任何一个点作为答案的可能，怎么办？
我们可以对整个序列进行遍历。遍历过程中将可能有用的答案加入\(S\)中，将一定没用的答案直接剔除。首先，我们可以先确定哪些是一定没用的答案：
- 距离超出\(m\)的。
- 前缀和更大的（这样的话差就会变小，也就是区间和会变小）。
抽象点讲，假设已经遍历到位置\(i\)，那么集合\(S\)内有决策点\(j\)，如果满足两者之一，即为没用的答案：
- \(j-i+1>m\)
- \(sum[i]>sum[j]\)
在单调队列中，我们只要可能有用的答案，我们一定会剔除掉没用的答案。所以，第一个条件我们可以通过队列的顺序保证，并且每次遍历时检查队头的情况；第二个条件我们可以考虑遍历时剔除掉队尾即可。为了让每个答案都不被预先抛弃，我们会将其放入入队列中。每个元素最多出入队各一次，时间复杂度为\(O(n)\)。
二维技巧
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
首先考虑不优秀的暴力：枚举左上端点\((i,j)\)，然后暴力计算\(n*n\)个点的极差，时间复杂度\(O(n^4)\)。
考虑优化：先从横行的角度进行处理，考虑维护每一行中的点作为右下端点，用两个单调队列处理出本行的最大最小值；之后从竖行的角度而言，求出一片区域（\(n^2\)）的极差更新答案即可。
// P2216.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#define pr pair<int, int>
using namespace std;
const int MX_A = 1020, MX_N = 200;
int a, b, n, mat[MX_A][MX_A], maxrow[MX_A][MX_A], minrow[MX_A][MX_A], Ymx[MX_A][MX_A], Ymi[MX_A][MX_A];
int main()
{
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> dqx, dqi;
for (int i = 1; i <= a; i++)
{
dqx.clear(), dqi.clear();
dqx.push_front(1), dqi.push_back(1);
for (int j = 2; j <= b; j++)
{
while (!dqx.empty() && mat[i][j] >= mat[i][dqx.back()])
dqx.pop_back();
while (!dqi.empty() && mat[i][j] <= mat[i][dqi.back()])
dqi.pop_back();
dqx.push_back(j), dqi.push_back(j);
while (!dqx.empty() && j - dqx.front() >= n)
dqx.pop_front();
while (!dqi.empty() && j - dqi.front() >= n)
dqi.pop_front();
if (j >= n)
maxrow[i][j - n + 1] = mat[i][dqx.front()], minrow[i][j - n + 1] = mat[i][dqi.front()];
}
}
for (int i = 1; i <= b - n + 1; i++)
{
dqx.clear(), dqi.clear();
dqx.push_front(1), dqi.push_back(1);
for (int j = 2; j <= a; j++)
{
while (!dqx.empty() && maxrow[j][i] >= maxrow[dqx.back()][i])
dqx.pop_back();
while (!dqi.empty() && minrow[j][i] <= minrow[dqi.back()][i])
dqi.pop_back();
dqx.push_back(j), dqi.push_back(j);
while (!dqx.empty() && j - dqx.front() >= n)
dqx.pop_front();
while (!dqi.empty() && j - dqi.front() >= n)
dqi.pop_front();
if (j >= n)
Ymx[j - n + 1][i] = maxrow[dqx.front()][i], Ymi[j - n + 1][i] = minrow[dqi.front()][i];
}
}
int ans = 2e9;
for (int i = 1; i <= a - n + 1; i++)
for (int j = 1; j <= b - n + 1; j++)
ans = min(ans, Ymx[i][j] - Ymi[i][j]);
printf("%d", ans);
return 0;
}
很多二维统计题都可以用这样的套路：点动成线，线动成面。