题目描述

给定一个 n×m 的二维矩阵 a，以及两个正整数 r 和 s，要求找出矩阵中所有 r×s 子矩阵的最大值，最终输出一个 (n-r+1)×(m-s+1) 的结果矩阵，其中每个元素对应原矩阵中对应位置 r×s 子矩阵的最大值。

解题思路

本题的核心难点是高效计算多个子矩阵的最大值，若直接暴力枚举每个子矩阵并遍历计算最大值，时间复杂度会达到 O(nmrs)，对于较大的矩阵会严重超时。因此采用两次单调队列滑动窗口的优化方案，将时间复杂度降至 O(nm)，具体思路如下：

第一步：行方向滑动窗口（计算每行局部最大值）

首先对矩阵的每一行单独处理，使用单调队列维护滑动窗口内的最大值。对于每一行，我们需要找出所有长度为 s 的滑动窗口的最大值，得到一个中间矩阵 row_max：

• row_max[i][j] 表示原矩阵第 i 行中，从第 j 列开始、长度为 s 的窗口的最大值。
• 中间矩阵 row_max 的维度为 n×(m-s+1)，因为每行有 m-s+1 个长度为 s 的窗口。

第二步：列方向滑动窗口（计算最终结果）

以第一步得到的 row_max 为基础，对每一列单独处理，同样使用单调队列维护滑动窗口内的最大值。此时窗口长度为 r，最终得到结果矩阵：

• result[i][j] 表示 row_max 第 j 列中，从第 i 行开始、长度为 r 的窗口的最大值，对应原矩阵中 (i,j) 位置开始的 r×s 子矩阵的最大值。
• 结果矩阵 result 的维度为 (n-r+1)×(m-s+1)，符合题目要求。

关键技术：单调队列

单调队列是一种特殊的队列，其内部元素始终保持单调递减（本题场景），用于高效维护滑动窗口的最大值，核心操作如下：

1. 移除过期元素：窗口滑动时，若队列头部元素对应的索引超出当前窗口范围，将其弹出。
2. 维护单调递减：加入新元素前，将队列尾部所有小于当前元素的元素弹出（这些元素不可能成为后续窗口的最大值）。
3. 记录最大值：当窗口长度达到要求时，队列头部元素即为当前窗口的最大值。

通过单调队列，每个元素仅入队和出队各一次，确保单次滑动窗口的时间复杂度为 O(k)（k 为序列长度）。

代码解析

1. 行方向滑动窗口计算 row_max

vector<vector<int>> row_max(n, vector<int>(m - s + 1));
for (int i = 0; i < n; ++i) {  // 遍历每一行
    deque<int> dq;  // 存储索引，保持对应值单调递减
    for (int j = 0; j < m; ++j) {
        // 移除窗口外的过期元素（窗口左边界为 j-s+1）
        while (!dq.empty() && dq.front() <= j - s) {
            dq.pop_front();
        }
        // 移除队列尾部小于当前元素的元素，维护单调递减
        while (!dq.empty() && a[i][dq.back()] <= a[i][j]) {
            dq.pop_back();
        }
        dq.push_back(j);  // 加入当前元素索引
        // 窗口长度达到 s，记录当前窗口最大值
        if (j >= s - 1) {
            row_max[i][j - s + 1] = a[i][dq.front()];
        }
    }
}

2. 列方向滑动窗口计算结果矩阵

vector<vector<int>> result(n - r + 1, vector<int>(m - s + 1));
for (int j = 0; j < m - s + 1; ++j) {  // 遍历 row_max 的每一列
    deque<int> dq;
    for (int i = 0; i < n; ++i) {
        // 移除窗口外的过期元素（窗口上边界为 i-r+1）
        while (!dq.empty() && dq.front() <= i - r) {
            dq.pop_front();
        }
        // 移除队列尾部小于当前元素的元素，维护单调递减
        while (!dq.empty() && row_max[dq.back()][j] <= row_max[i][j]) {
            dq.pop_back();
        }
        dq.push_back(i);
        // 窗口长度达到 r，记录当前窗口最大值（即 r×s 子矩阵的最大值）
        if (i >= r - 1) {
            result[i - r + 1][j] = row_max[dq.front()][j];
        }
    }
}

3. 输入输出优化

ios::sync_with_stdio(false);
cin.tie(nullptr);

关闭同步流和取消绑定，加快输入输出速度，应对大规模数据。

时间复杂度与空间复杂度

• 时间复杂度：O(nm)。行方向处理每一行的时间为 O(m)，共 n 行，耗时 O(nm)；列方向处理每一列的时间为 O(n)，共 (m-s+1) 列，耗时 O(nm)，总时间复杂度为 O(nm)。
• 空间复杂度：O(nm)。中间矩阵 row_max 占用 O(n(m-s+1)) 空间，最坏情况下（s=1）为 O(nm)；单调队列的空间为 O(min(n,m))，可忽略不计。

示例

输入

3 4
1 3 2 4
5 2 6 1
3 7 1 2
2 3

行方向处理（s=3）

• 第 0 行：窗口 [1,3,2]（max=3）、[3,2,4]（max=4）→ row_max[0] = [3,4]
• 第 1 行：窗口 [5,2,6]（max=6）、[2,6,1]（max=6）→ row_max[1] = [6,6]
• 第 2 行：窗口 [3,7,1]（max=7）、[7,1,2]（max=7）→ row_max[2] = [7,7]

列方向处理（r=2）

• 第 0 列：窗口 [3,6]（max=6）、[6,7]（max=7）→ result 第 0 列 = [6,7]
• 第 1 列：窗口 [4,6]（max=6）、[6,7]（max=7）→ result 第 1 列 = [6,7]

输出

6 6 
7 7 

该结果对应原矩阵中 4 个 2×3 子矩阵的最大值：

• [1,3,2;5,2,6] → max=6
• [3,2,4;2,6,1] → max=6
• [5,2,6;3,7,1] → max=7
• [2,6,1;7,1,2] → max=7

总结

本题通过两次单调队列滑动窗口，将二维子矩阵最大值问题拆解为行、列两个一维滑动窗口问题，大幅优化了时间复杂度。该思路可推广到类似的二维滑动窗口极值问题（如最小值、求和等），具有较强的通用性。