FakeMaxpooling - 题解

标签与难度

标签: 二维数据结构, 单调队列, 滑动窗口, 动态规划, 数论, 矩阵难度: 2000

题目大意喵~

主人你好呀，喵~ 这道题是这样的：

首先，我们要凭空想象一个 $n \times m$ 大小的矩阵，我们叫它 $A$ 好了。这个矩阵里的每个元素 $A_{i,j}$ 的值都非常特殊，它等于行号 $i$ 和列号 $j$ 的最小公倍数（least common multiple），也就是 $lcm(i, j)$ 呐。这里的 $i$ 和 $j$ 都是从 1 开始数的哦。

然后呢，题目会给我们一个整数 $k$ 。我们需要在这个 $n \times m$ 的大矩阵中，找出所有 $k \times k$ 大小的子矩阵（就像在棋盘上框出一个个小方格一样）。对于每一个这样的小方格，我们要找到里面的最大值。

最后一步，就是把所有这些找出来的最大值全部加起来，得到一个总和。把这个总和告诉我就好啦！

举个栗子：如果 $n=3, m=3, k=2$ ，那么矩阵 $A$ 就是：

\begin{pmatrix} lcm(1,1)=1 & lcm(1,2)=2 & lcm(1,3)=3 \\ lcm(2,1)=2 & lcm(2,2)=2 & lcm(2,3)=6 \\ lcm(3,1)=3 & lcm(3,2)=6 & lcm(3,3)=3 \end{pmatrix}

我们能找到 4 个 $2 \times 2$ 的小方格，它们的最大值分别是 2, 6, 6, 6。所以答案就是 $2+6+6+6=20$ ，喵~

解题思路分析

看到这道题，我的猫猫直觉告诉我，直接去遍历每一个 $k \times k$ 的小方格，再在里面找最大值，肯定会超时的说！你想呀，总共有 $(n-k+1) \times (m-k+1)$ 个小方格，每个方格里有 $k \times k$ 个元素。总的时间复杂度会是 $O(n \cdot m \cdot k^2)$ ，当 $n$ 和 $m$ 很大的时候，这可不得了，计算机会累坏的！

所以，我们需要一个更聪明的办法，喵！这种在“滑动窗口”里找最值的问题，通常都有一个神器可以解决，那就是——单调队列！

降维打击！从二维到一维

直接处理二维的窗口有点复杂，不如我们把它拆成两步，一步一步来，就像猫猫悄悄接近猎物一样，要有耐心呐。

第一步：处理每一行 我们可以先不管二维，只看每一行。对于第 $i$ 行，它就是一个长度为 $m$ 的一维数组。我们可以在这一行上，用一个大小为 $k$ 的滑动窗口，从左滑到右。对于每个窗口，我们都找出最大值。
这个 "一维滑动窗口最大值" 问题，正是单调队列的经典应用场景！我们可以用一个双端队列（deque），在 $O(m)$ 的时间复杂度内，求出第 $i$ 行所有大小为 $k$ 的窗口的最大值。
做完这一步，我们可以得到一个新的中间矩阵，我们叫它 row_max_matrix。row_max_matrix[i][j] 存储的是原始矩阵 $A$ 中，第 $i$ 行、从第 $j-k+1$ 列到第 $j$ 列这 $k$ 个元素中的最大值。
$\text{row\_max\_matrix}[i][j] = \max_{p=j-k+1}^{j} A_{i,p}$
第二步：处理每一列 现在我们有了 row_max_matrix。再来看看我们最初的目标：求一个 $k \times k$ 区域的最大值。一个以 $(r, c)$ 为右下角的 $k \times k$ 区域的最大值，可以表示为：
$\max_{\substack{r-k+1 \le i \le r \\ c-k+1 \le j \le c}} A_{i,j}$
这个式子可以等价地写成：
$\max_{i=r-k+1}^{r} \left( \max_{j=c-k+1}^{c} A_{i,j} \right)$
喵！你看，括号里的部分 max_{j=c-k+1}^{c} A_{i,j} 不就是我们第一步算出来的 row_max_matrix[i][c] 吗？
所以，原问题就转化成了：
$\max_{i=r-k+1}^{r} \text{row\_max\_matrix}[i][c]$
这又是一个一维滑动窗口最大值问题！只不过这次窗口是在 row_max_matrix 的某一列上，自上而下地滑动。
所以，我们对 row_max_matrix 的每一列，再做一次大小为 $k$ 的滑动窗口最大值计算。这样得到的结果，就是我们想要的每一个 $k \times k$ 子矩阵的最大值了！

单调队列是怎么工作的喵？

它是一个很神奇的队列，里面存的是元素的下标，并且它始终保持队列里下标对应的元素值是单调递减的。

入队：当一个新元素要进来时，我们会从队尾开始，把所有比它小的元素都踢出去，然后再让它进去。这样就保证了队列的单调性。
出队：队首的元素总是当前窗口里最大（或最老的最大）的。在窗口滑动时，我们要检查队首的元素是否已经滑出窗口范围了，如果是，就把它从队首踢出去。
取最大值：经过上面两步，任何时候，队首的元素就是当前窗口的最大值啦！

通过这两次华丽的降维打击，我们把整个问题的时间复杂度从 $O(n \cdot m \cdot k^2)$ 降到了 $O(n \cdot m)$ ，真是太棒了，喵~

总结一下我们的计划：

生成矩阵 A: 遍历 $i$ 从 1 到 $n$ ， $j$ 从 1 到 $m$ ，计算 $A_{i,j} = \text{lcm}(i, j)$ 。为了防止乘法溢出，最好用 (long long)i * j / gcd(i, j) 或者 (i / gcd(i, j)) * j 来算。
行处理: 创建一个新矩阵 row_max_matrix。对 $A$ 的每一行，使用单调队列计算所有大小为 $k$ 的窗口最大值，并存入 row_max_matrix 对应行的 k 到 m 列。
列处理与求和: 遍历 row_max_matrix 的每一列（从第 $k$ 列到第 $m$ 列）。对每一列，再次使用单调队列计算大小为 $k$ 的窗口最大值。每算出一个最大值，就把它累加到我们的总和 ans 里。
输出结果: 最后输出 ans 就大功告成啦！

代码实现

这是我根据上面的思路，精心为你准备的代码哦~ 注释写得很详细，希望能帮到你，喵！

cpp

#include <iostream>
#include <vector>
#include <numeric> // 为了 std::gcd
#include <deque>   // 为了使用双端队列

// 一个小助手函数，用来计算最小公倍数 (lcm)
// 使用 (a / gcd(a, b)) * b 的形式可以避免 a * b 溢出，更安全喵
long long calculate_lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    return static_cast<long long>(a) / std::gcd(a, b) * b;
}

int main() {
    // 使用 std::ios_base::sync_with_stdio(false) 和 cin.tie(nullptr) 可以让输入输出更快，对付大数据量很有用！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    std::cin >> n >> m >> k;

    // 1. 生成原始的 lcm 矩阵
    // 我们用 vector 来存储矩阵，更灵活安全喵
    std::vector<std::vector<int>> matrix(n + 1, std::vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            matrix[i][j] = calculate_lcm(i, j);
        }
    }

    // 2. 行处理：计算每行滑动窗口的最大值
    // 结果存放在一个新的矩阵 row_max_matrix 中
    std::vector<std::vector<int>> row_max_matrix(n + 1, std::vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        std::deque<int> window_q; // 单调队列，存储列的下标 j
        for (int j = 1; j <= m; ++j) {
            // 维护单调性：把队列尾部 <= 当前元素值的都踢出去
            while (!window_q.empty() && matrix[i][window_q.back()] <= matrix[i][j]) {
                window_q.pop_back();
            }
            window_q.push_back(j);

            // 移除越界元素：队首元素如果已经滑出窗口，就踢掉
            if (window_q.front() <= j - k) {
                window_q.pop_front();
            }

            // 当窗口形成后（即 j >= k），记录当前窗口的最大值
            if (j >= k) {
                row_max_matrix[i][j] = matrix[i][window_q.front()];
            }
        }
    }

    // 3. 列处理与求和：对 row_max_matrix 的每一列计算滑动窗口最大值
    long long total_sum = 0;
    // 我们只需要从第 k 列开始处理，因为 k*k 矩阵的右下角不可能在 k 列之前
    for (int j = k; j <= m; ++j) {
        std::deque<int> window_q; // 单调队列，存储行的下标 i
        for (int i = 1; i <= n; ++i) {
            // 维护单调性
            while (!window_q.empty() && row_max_matrix[window_q.back()][j] <= row_max_matrix[i][j]) {
                window_q.pop_back();
            }
            window_q.push_back(i);

            // 移除越界元素
            if (window_q.front() <= i - k) {
                window_q.pop_front();
            }

            // 当窗口形成后（即 i >= k），队首就是当前 k*k 子矩阵的最大值
            // 我们把它加到总和里
            if (i >= k) {
                total_sum += row_max_matrix[window_q.front()][j];
            }
        }
    }

    // 4. 输出最终结果
    std::cout << total_sum << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \times M)$
- 生成原始的 lcm 矩阵需要遍历 $N \times M$ 个元素，复杂度为 $O(N \times M)$ 。
- 行处理阶段，我们对 $N$ 行分别进行操作。每一行，每个元素最多进出单调队列一次，所以处理一行的复杂度是 $O(M)$ 。总共是 $O(N \times M)$ 。
- 列处理阶段同理，我们对 $M-k+1$ 列进行操作，每列的复杂度是 $O(N)$ 。总共也是 $O(N \times M)$ 。
- 所以总的时间复杂度是 $O(N \times M) + O(N \times M) + O(N \times M) = O(N \times M)$ ，非常高效！
空间复杂度: $O(N \times M)$
- 我们使用了 matrix 和 row_max_matrix 两个 $N \times M$ 大小的二维数组来存储数据。所以空间复杂度是 $O(N \times M)$ 。
- 单调队列本身的空间消耗最多是 $O(\max(N, M))$ ，与矩阵相比可以忽略不计。

知识点总结

这道题真是一次愉快的思维探险呢，喵~ 它教会了我们：

降维思想: 面对高维问题（比如二维矩阵），可以尝试将其分解成多个低维问题（一维数组）来解决。这种“分而治之”的策略在算法中非常有用！
滑动窗口最值: 这是单调队列最经典的用武之地。无论是求最大值还是最小值，单调队列都能在线性时间内完成，是优化暴力枚举的强大工具。
数论基础: 了解并正确计算最大公约数（GCD）和最小公倍数（LCM）是解决问题的第一步。lcm(a, b) = (a * b) / gcd(a, b) 这个公式要牢记在心，同时注意防止计算过程中的整数溢出。

希望这篇题解能让你对单调队列有更深的理解！如果还有不懂的地方，随时可以再来问我哦，喵~

FakeMaxpooling - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

降维打击！从二维到一维 ​

单调队列是怎么工作的喵？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​