二维滑动窗口与单调队列：从P2216理想正方形看矩阵最值优化

1. 项目概述：从一道经典题目看信息学竞赛的算法思维

最近在带学生刷信奥（信息学奥林匹克）题目，又翻到了这道P2216 [HAOI2007] 理想的正方形。这道题可以说是二维滑动窗口和单调队列的“典中典”，也是很多选手从一维思维迈向二维数据处理的关键一步。题目本身描述很简洁：给你一个a*b的整数矩阵，以及一个整数n，要求你在这个大矩阵中，找出所有n*n大小的正方形子矩阵，并计算每个子矩阵中最大值与最小值的差，最后输出所有差值中最小的那个。听起来是不是有点像在图像里找最“平滑”的一块区域？这背后考察的，远不止是简单的暴力遍历。

很多刚接触这道题的同学，第一反应就是四重循环暴力：枚举正方形左上角坐标(i, j)，再在这个n*n的范围内遍历找最大值和最小值。这个思路直观，但当a, b达到1000，n达到100时，计算量轻松突破百亿级别，必然超时。这就逼着我们去思考更优的算法。这道题的价值，就在于它完美地串联起了滑动窗口、单调队列这两个核心的数据结构思想，并且要求我们在二维空间里灵活运用。用C++实现它，不仅是对语法和STL的熟练度考验，更是对算法设计能力和空间思维的一次强化训练。无论你是正在备战CSP-J/S的选手，还是希望提升算法功底的开发者，吃透这道题，都会对处理矩阵类、区间最值类问题有质的帮助。

2. 核心算法思路拆解：降维打击与单调队列的精髓

2.1 为什么暴力法行不通？复杂度分析

我们先来算一笔账，彻底理解暴力法的瓶颈。假设矩阵大小为a*b，要找的正方形边长为n。

• 可能的正方形左上角坐标有(a-n+1)*(b-n+1)个。
• 对于每个正方形，我们需要遍历n*n个元素来寻找最大值和最小值。
• 因此，总的时间复杂度是O((a-n+1)*(b-n+1)*n²)。在极限数据a=b=1000, n=100时，计算量约为(901*901*10000) ≈ 8.1*10^9（81亿次）操作。这在竞赛的时限内（通常1秒~2秒）是完全不可能完成的。

问题的核心在于，对于每一个新的子正方形，我们都在“重复计算”。相邻的正方形区域有大量的重叠部分。我们的优化思路，就是利用这种重叠性，避免重复劳动。

2.2 一维滑动窗口与单调队列回顾

解决重复计算的关键工具是单调队列。我们先在简单的一维场景下理解它。假设有一个数组nums和一个长度为k的滑动窗口，我们需要快速得到每个窗口内的最大值。

暴力法是对每个窗口遍历k个元素，复杂度 O(nk)。而单调队列可以在 O(n) 时间内解决。它维护一个双端队列deque，里面存放的是数组元素的索引，并且保证这些索引对应的元素值是单调递减的（对于求最大值）。

算法过程如下：

1. 遍历数组，当前元素索引为i。
2. 移除队首所有不在当前窗口范围内的索引（即i - 队首索引 >= k）。
3. 从队尾开始，移除所有对应元素值小于等于nums[i]的索引（因为它们不可能再成为后续窗口的最大值了）。
4. 将当前索引i加入队尾。
5. 当i >= k-1时，队首索引对应的元素就是当前窗口的最大值。

这个过程中，每个元素最多入队一次、出队一次，所以均摊复杂度是 O(n)。求最小值只需将单调性改为递增即可。

2.3 从一维到二维的扩展思路

现在我们把问题扩展到二维。目标是快速得到一个n*n子矩阵的最大值和最小值。

我们可以采用一种降维的思想：

1. 第一步：预处理行方向上的最值。对于矩阵的每一行，我们用长度为n的滑动窗口求出该行所有连续n个元素的最大值和最小值。这样，我们得到了两个新的矩阵row_max和row_min。row_max[i][j]表示原矩阵第i行中，从第j列开始的连续n个元素的最大值。
2. 第二步：在列方向上聚合。现在，对于row_max矩阵的每一列，我们再用一个长度为n的滑动窗口，在垂直方向（行方向）上求这连续n个row_max[i][j]的最大值。这个结果，恰恰就是原矩阵中，以(i-n+1, j)为左上角的n*n子矩阵的最大值！同理，对row_min矩阵做列方向的滑动窗口最小值处理，就能得到每个子矩阵的最小值。

这个两步法，将二维问题分解为两个一维问题，每个一维问题都可以用 O(n) 的单调队列高效解决。总时间复杂度为O(a*b)，完美解决了暴力法的瓶颈。

注意：这里行列处理的顺序可以互换。也可以先对列做预处理，再对行做聚合。关键在于理解“降维”和“分解”的思想。

3. 代码实现与核心细节解析

理解了算法，我们来看C++实现。我会先给出完整的代码框架，然后逐一拆解关键部分。

#include <iostream> #include <cstdio> #include <deque> #include <algorithm> #include <climits> using namespace std; const int MAXN = 1005; int a, b, n; int val[MAXN][MAXN]; int row_max[MAXN][MAXN], row_min[MAXN][MAXN]; int final_max[MAXN][MAXN], final_min[MAXN][MAXN]; // 单调队列求滑动窗口最值，结果存入 res[][] // mp: 原矩阵， res：结果矩阵， rows：行数， cols：列数， len：窗口长度， isMax：是否求最大值 void monotonicQueue(int mp[][MAXN], int res[][MAXN], int rows, int cols, int len, bool isMax) { for (int i = 0; i < rows; ++i) { deque<int> dq; // 存储的是列索引 for (int j = 0; j < cols; ++j) { // 1. 维护队列范围，移除超出窗口的队首元素 if (!dq.empty() && j - dq.front() >= len) { dq.pop_front(); } // 2. 维护队列单调性 if (isMax) { // 求最大值：保持队列递减 while (!dq.empty() && mp[i][dq.back()] <= mp[i][j]) { dq.pop_back(); } } else { // 求最小值：保持队列递增 while (!dq.empty() && mp[i][dq.back()] >= mp[i][j]) { dq.pop_back(); } } // 3. 当前索引入队 dq.push_back(j); // 4. 当窗口形成时，记录结果 if (j >= len - 1) { res[i][j] = mp[i][dq.front()]; } } } } int main() { scanf("%d%d%d", &a, &b, &n); for (int i = 0; i < a; ++i) { for (int j = 0; j < b; ++j) { scanf("%d", &val[i][j]); } } // 第一步：对每一行，求长度为n的滑动窗口最值 // 注意：处理后的列范围是 [n-1, b-1] monotonicQueue(val, row_max, a, b, n, true); // 行最大值 monotonicQueue(val, row_min, a, b, n, false); // 行最小值 // 第二步：对 row_max 和 row_min 的每一“列”，在垂直方向求长度为n的滑动窗口最值 // 这里需要“转置”一下思维：把 row_max 的第j列看作一个一维数组 // 我们构造两个临时矩阵，其“行”是原矩阵的列 int tmp_max[MAXN][MAXN], tmp_min[MAXN][MAXN]; // 先进行“转置”操作，便于用同一个函数处理 for (int i = 0; i < a; ++i) { for (int j = n-1; j < b; ++j) { // 注意列起点是n-1 tmp_max[j][i] = row_max[i][j]; tmp_min[j][i] = row_min[i][j]; } } // 现在 tmp_max 的行数 = b，列数 = a。我们对它的每一“行”（即原矩阵的每一列）做滑动窗口 // 窗口长度依然是n，但处理的“数组长度”是a int newRows = b; // 原矩阵的列数 int newCols = a; // 原矩阵的行数 monotonicQueue(tmp_max, final_max, newRows, newCols, n, true); monotonicQueue(tmp_min, final_min, newRows, newCols, n, false); // 计算答案 int ans = INT_MAX; // final_max 和 final_min 的索引需要理解：final_max[i][j] 对应原矩阵中以 (j-n+1, i-n+1) 为左上角的子矩阵 // 其中 i 在 [n-1, b-1] 之间， j 在 [n-1, a-1] 之间 for (int i = n-1; i < b; ++i) { for (int j = n-1; j < a; ++j) { ans = min(ans, final_max[i][j] - final_min[i][j]); } } printf("%d\n", ans); return 0; }

3.1 单调队列函数的通用设计

上面的monotonicQueue函数是核心。它被设计成通用的，既能处理行，也能处理“列”（通过数据重排）。参数isMax用一个布尔值控制是求最大值还是最小值，避免了写两个几乎相同的函数。这里的关键细节是：

• deque<int> dq存储的是列索引（在第一步处理行时），或者行索引（在第二步处理转置后的列时）。这保证了我们能通过索引判断元素是否还在窗口内。
• 条件j - dq.front() >= len是“大于等于”，而不是“大于”。这是因为当窗口刚好滑动到使队首元素离开时，它就应该被移除。例如窗口长度len=3，当前j=3，队首索引为0，3-0 >= 3成立，索引0已不在窗口[1,3]内。
• 维护单调性时，用的是<=和>=。这意味着当遇到相等的元素时，我们会保留更靠右的那一个（因为旧的被弹出）。这对于 correctness 没有影响，但保证了信息的时效性。

3.2 索引变换与“转置”技巧

这是本题最容易混淆的地方。第一步后，我们得到row_max[i][j]，其中j的取值范围是[n-1, b-1]。因为只有从第n-1列开始，才能形成一个完整的长度为n的窗口。

第二步，我们需要对“列”进行操作。一个直观但繁琐的方法是再写一个专门处理列方向的单调队列函数。更清晰的做法是进行“转置”：将row_max的第j列数据，放到一个临时矩阵tmp_max的第j行。

// 原：row_max[i][j] 表示第i行，第j列开始的窗口最大值 // 转置后：tmp_max[j][i] = row_max[i][j] // 此时，tmp_max[j] 这个一维数组，就代表了原矩阵所有行在第j列上的“行最大值”序列。

然后，我们对tmp_max的每一行（即原矩阵的每一列）调用同一个monotonicQueue函数。函数会在这个“行”上做滑动窗口。处理完后，final_max[i][j]中的i对应原矩阵的列号，j对应原矩阵的行号，需要小心映射回原矩阵的子矩阵位置。

3.3 内存布局与性能考量

我们使用了多个MAXN*MAXN的静态数组。在竞赛中，通常MAXN设为1005或稍大一点，以避免边界问题。使用静态数组比vector稍快，但要注意不要开得过大导致栈溢出（大数组应开成全局变量，如本例所示）。

在单调队列的内部循环中，我们直接通过mp[i][dq.back()]访问元素。这里mp是一个二维数组参数，编译器能够高效地计算地址。确保你的遍历顺序（通常是行优先）与内存布局一致，以利用CPU缓存，提升性能。

4. 常见问题与调试技巧实录

即便理解了算法，实现时还是会遇到各种“坑”。下面是我和学生们在实战中总结出来的常见问题。

4.1 问题一：答案错误，差一两个点

可能原因1：索引范围计算错误。这是最常见的问题。最终遍历final_max和final_min求答案时，i和j的循环起始和终止条件必须精确对应有效的子矩阵左上角。

• 经过第一步行处理，有效列索引范围是[n-1, b-1]。
• 经过第二步列处理，有效行索引范围是[n-1, a-1]。
• 所以最终二重循环应为：

  for (int i = n-1; i < b; ++i) { // i 对应原矩阵列号 for (int j = n-1; j < a; ++j) { // j 对应原矩阵行号 ans = min(ans, final_max[i][j] - final_min[i][j]); } }

  你可以这样验证：当n=1时，循环应覆盖所有a*b个元素。上述代码中，i从0到b-1，j从0到a-1，符合预期。

可能原因2：单调队列弹出队首的条件判断错误。条件if (!dq.empty() && j - dq.front() >= len)中的>=如果写成>，会导致窗口大小实际为len+1时才弹出旧元素，造成结果错误。可以用一个简单的一维数组例子测试你的单调队列函数。

可能原因3：输入矩阵行列与题目描述相反。虽然题目描述通常是a行b列，但有时选手会下意识地按b行a列去读数据和定义数组。务必保持清晰，在代码注释中明确a是行数，b是列数。

4.2 问题二：运行超时（TLE）

可能原因1：用了endl而不是\n。在输出大量数据时，endl会刷新输出缓冲区，导致极大的性能开销。竞赛中一律使用\n或printf。

可能原因2：用了cin/cout而没有关闭同步。默认情况下，C++的iostream与C的stdio是同步的，这会影响速度。可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);来关闭同步，提升cin/cout速度。但更常见的做法是直接使用scanf和printf，它们通常更快。

可能原因3：数组过大且初始化耗时。如果MAXN设得很大（比如5000），并且多次清空整个数组，可能会带来可观的开销。非必要情况下，只需确保使用的部分被正确赋值即可。

可能原因4：算法复杂度退化。检查你的单调队列实现，确保每个元素确实只入队出队一次。如果在内层循环中不小心写成了从头遍历队列来维护单调性，复杂度就会退化为 O(n²)。

4.3 问题三：运行时错误（RE），如段错误

可能原因1：数组越界。这是导致段错误的主要原因。重点检查：

• 所有数组访问的下标是否在[0, MAXN-1]范围内。
• 在monotonicQueue函数中，给res[i][j]赋值时，是否确保了j >= len - 1。对于j < len-1的位置，我们没有赋值，如果后续不小心读到，可能是随机值。
• 在“转置”操作中，tmp_max[j][i]的j和i是否可能超出tmp_max的定义范围？在我们的设计中，tmp_max第一维大小是MAXN（>=b），第二维也是MAXN(>=a)，且j在[n-1, b-1]，i在[0, a-1]，所以是安全的。

可能原因2：栈溢出。如果大数组（如int arr[1000][1000]）开在main函数内部，可能会占用过多栈空间（约4MB），导致程序崩溃。解决方案是将大数组定义为全局变量（在函数外部），这样它们存储在堆区，空间更大。

4.4 调试技巧与测试数据设计

1. 设计小规模测试数据：用a=3, b=3, n=2这样的小矩阵，手动计算所有2*2子矩阵的最值差，与程序输出对比。这是定位逻辑错误最快的方法。
2. 打印中间结果：在第一步行处理结束后，打印出row_max和row_min矩阵，看是否符合预期。同样，在转置后、第二步处理前后也打印关键数据。
3. 边界测试：
   • n=1：此时答案应为整个矩阵的最大值减最小值。
   • n=a=b：此时只有一个子矩阵，答案即为该矩阵自身的极差。
   • n等于a或b：此时子矩阵在某个方向上无法滑动，检查你的循环是否还能正确运行。
4. 对拍：写一个暴力算法（四重循环），用于生成小随机数据并对比结果。这是竞赛中验证正确性的黄金标准。

5. 算法扩展与同类问题举一反三

掌握了这道题，你其实就掌握了一类问题的通解。单调队列在滑动窗口最值问题上是“大杀器”。我们可以看看它的变体和应用：

5.1 高维扩展

理论上，对于d维空间中的一个超立方体子区域，要求最值，我们可以通过连续d次一维单调队列处理来降维求解，时间复杂度为 O(d * N)，其中 N 是总数据量。当然，维度过高时，代码复杂度和常数会增大。

5.2 同类问题链接

1. 洛谷 P1886 滑动窗口 /【模板】单调队列：这是一维情况的模板题，必须熟练掌握。
2. 洛谷 P2032 扫描：可以看作是一维滑动窗口最大值的简单应用。
3. 求矩阵中所有子矩阵的最大值/最小值：如果没有固定边长n，而是要求所有可能的子矩阵，那问题就完全不同了，通常会用到单调栈，例如洛谷 P4147 玉蟾宫（最大全1子矩阵）。

5.3 在动态规划中的应用

单调队列可以优化一类特殊的动态规划，即状态转移方程形如dp[i] = max/min{ dp[j] + f(i, j) } (i - j <= k)的问题，其中k是一个窗口大小。这时的dp[j]可以看作一个值，用单调队列维护窗口内的最优dp[j]。例如洛谷 P1725 琪露诺、P3572 [POI2014] PTA-Little Bird。

5.4 使用STLdeque的注意事项

我们代码中使用了std::deque。在竞赛中，为了极致的速度，有些选手会手写一个循环数组来实现双端队列，避免STL的开销。但对于本题的数据规模，deque完全足够。需要注意的是，deque的pop_front()和pop_back()是 O(1) 的，但随机访问比vector稍慢，不过我们只访问队首和队尾，所以没问题。

最后，关于这道题，我个人最深的体会是：算法竞赛中，优化往往来自于对“重复计算”的敏锐洞察和“数据结构”的巧妙运用。单调队列本身并不复杂，但将它应用到二维场景，需要清晰的降维思维和对索引映射的耐心推敲。在写这类代码时，我习惯先用注释把每个数组、每个索引的确切含义写清楚，比如“row_max[i][j]: 原矩阵第i行，从第j列开始向右n个元素的最大值”。这能极大减少思维混乱。另外，一定要自己构造几个极端但微小的测试案例，比如n等于1或等于矩阵边长的情况，跑一遍程序，看看边界是否牢固。这道题吃透了，以后再遇到需要快速查询矩形区域最值的问题，你心里就有底了。