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

1. 项目概述从一道经典题目看信息学竞赛的算法思维最近在带学生刷信奥信息学奥林匹克题目又翻到了这道P2216 [HAOI2007] 理想的正方形。这道题可以说是二维滑动窗口和单调队列的“典中典”也是很多选手从一维思维迈向二维数据处理的关键一步。题目本身描述很简洁给你一个a*b的整数矩阵以及一个整数n要求你在这个大矩阵中找出所有n*n大小的正方形子矩阵并计算每个子矩阵中最大值与最小值的差最后输出所有差值中最小的那个。听起来是不是有点像在图像里找最“平滑”的一块区域这背后考察的远不止是简单的暴力遍历。很多刚接触这道题的同学第一反应就是四重循环暴力枚举正方形左上角坐标(i, j)再在这个n*n的范围内遍历找最大值和最小值。这个思路直观但当a, b达到1000n达到100时计算量轻松突破百亿级别必然超时。这就逼着我们去思考更优的算法。这道题的价值就在于它完美地串联起了滑动窗口、单调队列这两个核心的数据结构思想并且要求我们在二维空间里灵活运用。用C实现它不仅是对语法和STL的熟练度考验更是对算法设计能力和空间思维的一次强化训练。无论你是正在备战CSP-J/S的选手还是希望提升算法功底的开发者吃透这道题都会对处理矩阵类、区间最值类问题有质的帮助。2. 核心算法思路拆解降维打击与单调队列的精髓2.1 为什么暴力法行不通复杂度分析我们先来算一笔账彻底理解暴力法的瓶颈。假设矩阵大小为a*b要找的正方形边长为n。可能的正方形左上角坐标有(a-n1)*(b-n1)个。对于每个正方形我们需要遍历n*n个元素来寻找最大值和最小值。因此总的时间复杂度是O((a-n1)*(b-n1)*n²)。在极限数据ab1000, n100时计算量约为(901*901*10000) ≈ 8.1*10^981亿次操作。这在竞赛的时限内通常1秒~2秒是完全不可能完成的。问题的核心在于对于每一个新的子正方形我们都在“重复计算”。相邻的正方形区域有大量的重叠部分。我们的优化思路就是利用这种重叠性避免重复劳动。2.2 一维滑动窗口与单调队列回顾解决重复计算的关键工具是单调队列。我们先在简单的一维场景下理解它。假设有一个数组nums和一个长度为k的滑动窗口我们需要快速得到每个窗口内的最大值。暴力法是对每个窗口遍历k个元素复杂度 O(nk)。而单调队列可以在 O(n) 时间内解决。它维护一个双端队列deque里面存放的是数组元素的索引并且保证这些索引对应的元素值是单调递减的对于求最大值。算法过程如下遍历数组当前元素索引为i。移除队首所有不在当前窗口范围内的索引即i - 队首索引 k。从队尾开始移除所有对应元素值小于等于nums[i]的索引因为它们不可能再成为后续窗口的最大值了。将当前索引i加入队尾。当i k-1时队首索引对应的元素就是当前窗口的最大值。这个过程中每个元素最多入队一次、出队一次所以均摊复杂度是 O(n)。求最小值只需将单调性改为递增即可。2.3 从一维到二维的扩展思路现在我们把问题扩展到二维。目标是快速得到一个n*n子矩阵的最大值和最小值。我们可以采用一种降维的思想第一步预处理行方向上的最值。对于矩阵的每一行我们用长度为n的滑动窗口求出该行所有连续n个元素的最大值和最小值。这样我们得到了两个新的矩阵row_max和row_min。row_max[i][j]表示原矩阵第i行中从第j列开始的连续n个元素的最大值。第二步在列方向上聚合。现在对于row_max矩阵的每一列我们再用一个长度为n的滑动窗口在垂直方向行方向上求这连续n个row_max[i][j]的最大值。这个结果恰恰就是原矩阵中以(i-n1, 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) { dequeint 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-n1, i-n1) 为左上角的子矩阵 // 其中 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用一个布尔值控制是求最大值还是最小值避免了写两个几乎相同的函数。这里的关键细节是dequeint dq存储的是列索引在第一步处理行时或者行索引在第二步处理转置后的列时。这保证了我们能通过索引判断元素是否还在窗口内。条件j - dq.front() len是“大于等于”而不是“大于”。这是因为当窗口刚好滑动到使队首元素离开时它就应该被移除。例如窗口长度len3当前j3队首索引为03-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]); } }你可以这样验证当n1时循环应覆盖所有a*b个元素。上述代码中i从0到b-1j从0到a-1符合预期。可能原因2单调队列弹出队首的条件判断错误。条件if (!dq.empty() j - dq.front() len)中的如果写成会导致窗口大小实际为len1时才弹出旧元素造成结果错误。可以用一个简单的一维数组例子测试你的单调队列函数。可能原因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第一维大小是MAXNb第二维也是MAXN(a)且j在[n-1, b-1]i在[0, a-1]所以是安全的。可能原因2栈溢出。如果大数组如int arr[1000][1000]开在main函数内部可能会占用过多栈空间约4MB导致程序崩溃。解决方案是将大数组定义为全局变量在函数外部这样它们存储在堆区空间更大。4.4 调试技巧与测试数据设计设计小规模测试数据用a3, b3, n2这样的小矩阵手动计算所有2*2子矩阵的最值差与程序输出对比。这是定位逻辑错误最快的方法。打印中间结果在第一步行处理结束后打印出row_max和row_min矩阵看是否符合预期。同样在转置后、第二步处理前后也打印关键数据。边界测试n1此时答案应为整个矩阵的最大值减最小值。nab此时只有一个子矩阵答案即为该矩阵自身的极差。n等于a或b此时子矩阵在某个方向上无法滑动检查你的循环是否还能正确运行。对拍写一个暴力算法四重循环用于生成小随机数据并对比结果。这是竞赛中验证正确性的黄金标准。5. 算法扩展与同类问题举一反三掌握了这道题你其实就掌握了一类问题的通解。单调队列在滑动窗口最值问题上是“大杀器”。我们可以看看它的变体和应用5.1 高维扩展理论上对于d维空间中的一个超立方体子区域要求最值我们可以通过连续d次一维单调队列处理来降维求解时间复杂度为 O(d * N)其中 N 是总数据量。当然维度过高时代码复杂度和常数会增大。5.2 同类问题链接洛谷 P1886 滑动窗口 /【模板】单调队列这是一维情况的模板题必须熟练掌握。洛谷 P2032 扫描可以看作是一维滑动窗口最大值的简单应用。求矩阵中所有子矩阵的最大值/最小值如果没有固定边长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或等于矩阵边长的情况跑一遍程序看看边界是否牢固。这道题吃透了以后再遇到需要快速查询矩形区域最值的问题你心里就有底了。