1314. Matrix Block Sum

Given a m x n matrix mat and an integer k, return  a matrix  answer  where each  answer[i][j]  is the sum of all elements  mat[r][c]  for :

  • i - k <= r <= i + k,
  • j - k <= c <= j + k, and
  • (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

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

这道题给了一个 m by n 的二维数组 mat 和一个正整数k,现在让返回一个 answer 数组,使得 answer[i][j] 是原数组 mat 中以 (i, j) 为中心,2k+1 为边长的正方形区域的数字之和。英文原版题目表示的不太容易理解,但是可以根据给定的例子来验证自己的理解,美中不足的是例子中没有提供分析,难怪论坛上有人吐槽说看不懂题意。由于 (i, j) 的位置和k的大小不确定,所以这个正方形大小不确定,若 (i, j) 在边缘位置,则边长为k的正方形区域就会缺失一些数字,比如例子1。还有就是若k比较大,则每个位置的正方形区域有可能都涵盖了整个 mat 数组,则所有位置的值都是原 mat 数组的所有数字之和,比如例子2。

其实这道题的本质就是要快速的计算任意一个区间和,也就是要建立二维的累加和数组,对于一维数组计算任意子数组的方法,想必大家都比较熟悉,这里二维的原理也是一样,只不过计算方法上稍稍复杂一些。为了更好的处理边界,这里使用一个 m+1 by n+1 的二维数组 sums 来表示累加和数组,对于某个 (i, j) 位置的更新方法是其在 mat 中对应位置上的值加上 sums[i-1][j] 和 sums[i][j-1],并减去 sums[i-1][j-1]。更新完了累加和数组,就可以来快速计算任意区间和了,要求的正方形区域中心位置是 (i, j),边长是 2k+1,现在要计算出正方形区间的右下顶点和左上顶点。

由于前面提到了这个正方形区间可能不会完全存在,即当中心点位于 mat 数组的边缘时,那么就一定有一部分是不存在的,所以要找出该正方形区间映射到 mat 数组上的区间。该正方形区间的右下顶点的坐标为 (i+k, j+k),但是这个坐标不能超过 mat 数组的最右下角 (m-1, n-1),所以正确的右下顶点坐标为 (min(m-1, i+k), min(n-1, j+k))。同理,该正方形区间的左上顶点的坐标为 (i-k, j-k),但是这个坐标不能小于 mat 数组的最左上角 (0, 0),所以正确的左上顶点坐标为 (max(0, i-k), max(0, j-k)),知道了子区间的左上和右下点的位置,就可以利用累加和数组快速求出区间和了,假设左上顶点坐标为 (p, q),右下顶点坐标为 (x, y),则区间和应该为 sums[x + 1][y + 1] - sums[x + 1][q] - sums[p][y + 1] + sums[p][q],参见代码如下:

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> sums(m + 1, vector<int>(n + 1)), res(m, vector<int>(n));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                sums[i][j] = mat[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int x = min(m - 1, i + k), y = min(n - 1, j + k);
                int p = max(0, i - k), q = max(0, j - k);
                res[i][j] = sums[x + 1][y + 1] - sums[x + 1][q] - sums[p][y + 1] + sums[p][q];
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1314

类似题目:

Stamping the Grid

参考资料:

https://leetcode.com/problems/matrix-block-sum/

https://leetcode.com/problems/matrix-block-sum/discuss/500833/C%2B%2B-prefix-sum-with-explanation

https://leetcode.com/problems/matrix-block-sum/discuss/477041/Java-Prefix-sum-with-Picture-explain-Clean-code-O(m*n)

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation