「力扣」第 1314 题:矩阵区域和(简单)

liweiwei1419 ... 2022-1-6 前缀和
  • 前缀和
About 2 min

参考「力扣」第 304 题:“二维区域和检索 - 矩阵不可变” (opens new window) 的做法。

# 题目描述

给你一个 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]]
1
2

示例 2:

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

提示:

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

# 思路分析

  • 先计算前缀和矩阵;
  • 再计算有效区域的左上角以及右下角的坐标;
  • 再使用前缀和矩阵以 O(1)O(1) 复杂度计算区域之和。

参考代码

import java.util.Arrays;

public class Solution {

    /**
     * 前缀和矩阵
     */
    private int[][] preSum;

    public int[][] matrixBlockSum(int[][] mat, int K) {
        // 行数和列数不用特判,因为题目已经说了不为 0
        int rows = mat.length;
        int cols = mat[0].length;

        // 初始化的时候多设置一行,多设置一列
        preSum = new int[rows + 1][cols + 1];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                preSum[i + 1][j + 1] = preSum[i + 1][j] + preSum[i][j + 1] - preSum[i][j] + mat[i][j];
            }
        }

        int[][] res = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 左上角横纵坐标
                int row1 = Math.max(i - K, 0);
                int col1 = Math.max(j - K, 0);

                // 右下角横纵坐标
                int row2 = Math.min(i + K, rows - 1);
                int col2 = Math.min(j + K, cols - 1);
                res[i][j] = sumRegion(row1, col1, row2, col2);
            }
        }
        return res;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2 + 1][col2 + 1]
                - preSum[row1][col2 + 1]
                - preSum[row2 + 1][col1]
                + preSum[row1][col1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

复杂度分析

  • 时间复杂度:O(MN)O(MN),这里 MM 是矩阵的行数,NN 是矩阵的列数;
  • 空间复杂度:O(MN)O(MN)
Last update: January 14, 2022 00:19
Contributors: liweiwei1419