LeetCode 1314. 矩阵区域和

Categories:

题目描述
思路分析
1. 解法一：二维前缀和（推荐）
相似题目

题目描述

✅ 1314. 矩阵区域和

思路分析

解法一：二维前缀和（推荐）

核心思路：

构建二维前缀和 sum，用于 O(1) 求任意子矩形和。

对每个位置 (i, j)，计算边界矩形 [i-k, i+k] x [j-k, j+k] 的和。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 为矩阵行列数。

空间复杂度：O(mn)。

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int r1 = Math.max(0, i - k);
                int c1 = Math.max(0, j - k);
                int r2 = Math.min(m - 1, i + k);
                int c2 = Math.min(n - 1, j + k);

                res[i][j] = sum[r2 + 1][c2 + 1] - sum[r1][c2 + 1] - sum[r2 + 1][c1] + sum[r1][c1];
            }
        }
        return res;
    }
}

func matrixBlockSum(mat [][]int, k int) [][]int {
    m := len(mat)
    n := len(mat[0])
    sum := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        sum[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1]
        }
    }

    res := make([][]int, m)
    for i := 0; i < m; i++ {
        res[i] = make([]int, n)
        for j := 0; j < n; j++ {
            r1 := max(0, i-k)
            c1 := max(0, j-k)
            r2 := min(m-1, i+k)
            c2 := min(n-1, j+k)
            res[i][j] = sum[r2+1][c2+1] - sum[r1][c2+1] - sum[r2+1][c1] + sum[r1][c1]
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
304. 二维区域和检索 - 矩阵不可变	中等	前缀和
1292. 元素和小于等于阈值的正方形的最大边长	中等	前缀和
1277. 统计全为 1 的正方形子矩阵	中等	DP
221. 最大正方形	中等	DP
363. 矩形区域不超过 K 的最大数值和	困难	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/12052563