【前缀和】矩阵区域和

1314. 矩阵区域和

1314. 矩阵区域和

​ 给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

解题思路

​ 首先我们要明白题目要我们干什么，其实就是求出矩阵中每个元素，它向外拓展 k 个单位之后形成的区域的总和，如下图中以元素 4 为例，如果 k = 1 的话的情况：

​ 那其实这道题我们就可以用之前学过的二维前缀和来解决，大体思路都是一样的，虽然我们给过模板，但是切记不要死记硬背，要理解模板是怎么来的！

​ 下面的推导，统一使用以上图中元素 4 为中心，k=1 的例子来推导！

​ 还是一样，首先我们需要一个二维的 dp 表来记录前缀和，而 dp[i][j] 就表示从 [0, 0] 到 [i, j] 的元素总和。

​ 根据状态表示和区域的累加，可以得到 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i][j]，这个和模板题是类似的，这里就不细讲了！

​ 接着我们再创建一个二维数组 ret，用于记录每个位置的区域和作为函数返回值的，此时和二维前缀和模板题不同的是，我们这次要求的区间需要我们自己去求出来，其实也不难，只要求出了要求的区域的左上角和右下角两个坐标，就能得到这个区间的信息了，如下图所示：

​ 也就是说，我们要求出图中的 x1、y1、x2、y2，但问题是，有可能这个区间的一部分是越界的，但是我们只要有效区间，所以我们需要做处理而不能单纯的让 x1 = 中心坐标 - k 这样子去计算，会出错的！

​ 那么该如何灵活的计算这个可能越界的坐标情况呢❓❓❓

​ 其实非常简单，首先假设中心元素 4 的坐标是 [i, j]，然后做法如下所示：

​ 以左上角为例，如果 i - k < 0，或者 j - k < 0，那么不用说肯定是越界了，此时我们只需要让 x1 = 0 或者 y1 = 0，但是如果我们去用 if 语句进行判断的话，其实是比较麻烦的，所以我们这里借用最值函数 max()，就让 x1 = max(0, i - k)，让 y1 = max(0, j - k)，这样子一旦 i - k < 0 或者 j - k < 0 了，那么它们就直接等于 0 了，就一定在二维数组的有效区间内！

​ 同理，右下角也是一样的，假设矩阵有 m 行 n 列，那么因为右下角的越界情况是 i + k ≥ m 或者 j + k ≥ n，所以我们需要用的最值函数是 min()，然后让 x2 = min(m - 1, i + k)，让 y2 = min(n - 1, j + k)，这样子一来一旦越界了，最后它们得到的值其实就是最后一行或者最后一列的坐标！

​ 计算出 x1、y1、x2、y2 之后，问题就和二维前缀和模板题是一样的了，根据状态表示，我们要求的区间 [x1, y1] 到 [x2, y2] 其实就是用几个区间进行相减即可，具体操作和二维前缀和模板题是类似的，这里不再赘述！

​ 所以结果 ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]。

​ 最后要注意的是，因为 dp 数组我们是开辟了虚拟行列的，所以 要注意和原数组 mat 以及 ret 的下标映射关系！

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 创建有虚拟行列的二维dp表

        // 前缀和预处理（处理dp表从下标1开始遍历，所以要注意和原数组mat的下标映射关系）
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];

        // 结果集的计算，下标从0开始，所以要注意和dp表的下标映射关系
        vector<vector<int>> ret(m, vector<int>(n)); // 创建结果集二维数组
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                // 先计算区间坐标，然后为了和dp表的映射关系，直接对这些坐标加一
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;

                // 状态转移方程计算（注意映射关系）
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
};