C++ 二维滑动窗口求最大差值矩形（单调队列优化）

好的，我们一步一步来分析这个题目。 ## 🧠 题目理解 题目叫做“理想的长方形”，其实问题是要我们**找最大值与最小值差值最大的一个 x × y 子矩形**，并输出这个最大差值。 注意样例输出是 17，意味着在整个矩阵中，某个 2×2 子矩形里最大值和最小值差为 17，且这个 17 是所有 x×y 子矩形中最大的差值。 --- ## 📐 问题分析 ### 核心难点 - 数据规模：`n, m ≤ 1000`，所以直接暴力枚举所有 x×y 子矩形，再分别求最大最小值，复杂度大约为 `O(n * m * x * y)`，这肯定超时。 - 我们需要**预处理**，快速得到任意子矩形的最大值和最小值。 ### 常用思路 **二维滑动窗口** + **单调队列** 可以分两步： 1. **对每一行**，使用单调队列求出长度为 y 的滑动窗口内的最大值和最小值。 2. **对每一列**，再在行处理的结果上，使用单调队列求出长度为 x 的滑动窗口内的最大值和最小值。 这样我们就能得到所有 x×y 子矩形的最大值和最小值矩阵，然后就很容易求出最大差值。 --- ## 📦 实现步骤（C++） ### 1️⃣ 定义输入输出 使用 `scanf`/`printf` 加速。 ### 2️⃣ 定义两个二维数组 - `maxVal[i][j]`：以 (i, j) 为右下角的 x×y 子矩形的最大值 - `minVal[i][j]`：对应最小值 ### 3️⃣ 按行处理滑动窗口 - 对每一行，计算长度为 y 的滑动窗口最大值和最小值，存入临时数组。 ### 4️⃣ 按列处理滑动窗口 - 在刚才行处理的结果上，每列再使用长度为 x 的滑动窗口。 ### 5️⃣ 求最大差值 遍历 `maxVal` 和 `minVal` 对应位置，求 `maxVal[i][j] - minVal[i][j]` 的最大值。 --- ## 💻 C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N][N]; int row_max[N][N], row_min[N][N]; int col_max[N][N], col_min[N][N]; int main() { int n, m, x, y; scanf("%d%d%d%d", &n, &m, &x, &y); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &a[i][j]); } } // 第一步：按行滑动窗口，求每行长度为y的最大最小 for (int i = 1; i <= n; ++i) { deque<int> dq_max, dq_min; for (int j = 1; j <= m; ++j) { // 维护最大值队列 while (!dq_max.empty() && a[i][dq_max.back()] <= a[i][j]) dq_max.pop_back(); dq_max.push_back(j); if (dq_max.front() < j - y + 1) dq_max.pop_front(); // 维护最小值队列 while (!dq_min.empty() && a[i][dq_min.back()] >= a[i][j]) dq_min.pop_back(); dq_min.push_back(j); if (dq_min.front() < j - y + 1) dq_min.pop_front(); if (j >= y) { row_max[i][j - y + 1] = a[i][dq_max.front()]; row_min[i][j - y + 1] = a[i][dq_min.front()]; } } } // 第二步：按列滑动窗口，求长度为x的最大最小 // 注意：列处理是在 row_max 和 row_min 的基础上进行 int new_m = m - y + 1; for (int j = 1; j <= new_m; ++j) { deque<int> dq_max, dq_min; for (int i = 1; i <= n; ++i) { // 最大值 while (!dq_max.empty() && row_max[dq_max.back()][j] <= row_max[i][j]) dq_max.pop_back(); dq_max.push_back(i); if (dq_max.front() < i - x + 1) dq_max.pop_front(); // 最小值 while (!dq_min.empty() && row_min[dq_min.back()][j] >= row_min[i][j]) dq_min.pop_back(); dq_min.push_back(i); if (dq_min.front() < i - x + 1) dq_min.pop_front(); if (i >= x) { col_max[i - x + 1][j] = row_max[dq_max.front()][j]; col_min[i - x + 1][j] = row_min[dq_min.front()][j]; } } } // 第三步：求最大差值 int ans = 0; int new_n = n - x + 1; for (int i = 1; i <= new_n; ++i) { for (int j = 1; j <= new_m; ++j) { ans = max(ans, col_max[i][j] - col_min[i][j]); } } printf("%d\n", ans); return 0; } ``` --- ## ✅ 复杂度分析 - 每一行滑动窗口：`O(n * m)` - 每一列滑动窗口：`O(n * (m - y + 1))` - 总复杂度：大约 `O(n * m)`，可接受。 --- ## ⚠️ 常见陷阱与开发建议 1. **数组下标从1开始**：方便处理边界，避免越界检查。 2. **deque 清空**：确保每个新行或新列的单调队列是空的。 3. **边界条件**：当 `j >= y` 或 `i >= x` 时才记录结果。 4. **内存使用**：`N=1010`，二维数组没问题，但若N更大可考虑只保留必要行/列的数据。 5. **输入输出优化**：使用 `scanf`/`printf` 而不是 `cin`/`cout`（或者关闭同步流）。 --- ## 📎 推荐学习资源 - [C++ STL deque 文档](https://en.cppreference.com/w/cpp/container/deque) - [二维滑动窗口问题汇总](https://oi-wiki.org/ds/monotonous-queue/) - 练习题目：洛谷 P1886 滑动窗口 /【模板】单调队列 --- ######[AI写代码神器 | 1548点数解答 | 2026-07-05 10:19:20]