LeetCode 1314. 矩阵区域和

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
数组 矩阵 前缀和

题目描述

✅ 1314. 矩阵区域和

image-20260929080506343

题意分析

对矩阵每个位置 (i, j)，求行号位于 [i-k, i+k] 且列号位于 [j-k, j+k] 的所有合法格子之和。行、列距离分别受限，区域是矩形，包含对角方向的格子。

超出矩阵的部分不参与求和，因此靠边区域会被裁小，矩阵也不一定为正方形。返回与输入同尺寸的矩阵，各答案都依据原矩阵计算，不能把已算出的区域和当成后续输入。

解法：二维前缀和

核心思路

[!blue]

不同中心的区域大量重叠，逐区间相加会重复读取许多格子。用二维前缀和保存公共部分：prefix[i][j] 表示前 i 行、前 j 列的矩形总和，前缀表比原矩阵多一行一列，零行、零列代表空区域。

构造一个前缀时，先加上方前缀和左侧前缀，两者重复计算了左上角的交集，所以减去左上前缀，再加当前原格子。按行列递增填表时，这三个依赖都已经计算完。

每次查询先把上下左右限制到矩阵边界，得到闭区间 [r1, r2] × [c1, c2]。从覆盖右下角的大前缀 prefix[r2 + 1][c2 + 1] 出发，减去目标上方部分 prefix[r1][c2 + 1]，再减去左侧部分 prefix[r2 + 1][c1]；左上交集被减了两次，最后加回 prefix[r1][c1]。

这四项恰好让目标矩形保留一次、外部格子抵消为零。前缀下标按行列数量定义，闭区间的右下端要加一；额外零行零列让贴着上边或左边的查询也能使用同一个公式。

每个中心只需计算裁剪边界和读取四项前缀，得到答案后写入新矩阵。即使 k 很大使多个区域覆盖整个矩阵，也无需重复扫描它们的内部。

解题步骤

  1. 建立 (rows + 1) × (cols + 1) 的前缀表，首行首列保持零。
  2. 逐格按“上方加左侧、减左上重叠、加原元素”填表。
  3. 对每个中心，用行数裁剪上下边界，用列数裁剪左右边界。
  4. 按四项容斥公式计算矩形和，写入同尺寸结果矩阵的当前位置。
  5. 全部位置处理后返回结果。

代码实现

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int rows = mat.length;
        int cols = mat[0].length;
        // 多出的零行零列表示空区域，统一容斥边界。
        int[][] prefix = new int[rows + 1][cols + 1];

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

        int[][] answer = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 四条边分别限制到矩阵内，行列上界不能混用。
                int row1 = Math.max(0, i - k);
                int row2 = Math.min(rows - 1, i + k);
                int col1 = Math.max(0, j - k);
                int col2 = Math.min(cols - 1, j + k);

                // 减去上方和左侧，再加回被减了两次的左上重叠。
                answer[i][j] =
                        prefix[row2 + 1][col2 + 1]
                                - prefix[row1][col2 + 1]
                                - prefix[row2 + 1][col1]
                                + prefix[row1][col1];
            }
        }

        return answer;
    }
}

func matrixBlockSum(mat [][]int, k int) [][]int {
    rows, cols := len(mat), len(mat[0])
    // 多出的零行零列表示空区域，统一容斥边界。
    prefix := make([][]int, rows+1)
    for i := range prefix {
        prefix[i] = make([]int, cols+1)
    }

    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + mat[i-1][j-1]
        }
    }

    answer := make([][]int, rows)
    for i := 0; i < rows; i++ {
        answer[i] = make([]int, cols)
        for j := 0; j < cols; j++ {
            // 四条边分别限制到矩阵内，行列上界不能混用。
            row1, row2 := maxInt(0, i-k), minInt(rows-1, i+k)
            col1, col2 := maxInt(0, j-k), minInt(cols-1, j+k)
            // 减去上方和左侧，再加回被减了两次的左上重叠。
            answer[i][j] = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]
        }
    }
    return answer
}

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

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

复杂度分析

  • 时间复杂度：$O(mn)$，前缀构造与所有查询各遍历矩阵一次。
  • 空间复杂度：前缀表占 $O(mn)$，结果矩阵另占同阶空间。

关键点总结

[!green]

  • 前缀坐标是行列数量，闭区间右下角需要加 1。
  • 减去上方和左侧后，左上重叠区域要加回一次。
  • 行数与列数分别用于各自边界，不能混用。
  • 只读取原矩阵，结果写入新矩阵。

易错点总结

[!yellow]

  • 漏掉左上补偿：内部窗口会被多减一块。
  • 没有截断越界边界：大 k 或靠边中心可能访问非法下标。
  • 把答案也开成多一行多一列：哨兵只属于前缀表，返回尺寸仍是原矩阵尺寸。

相似题目

题目 难度 关联与区别
304. 二维区域和检索 - 矩阵不可变 中等 二维前缀和可常数时间查询每个裁剪后的邻域矩形和。
661. 图片平滑器 简单 原题固定3×3窗口并求平均，本题窗口半径可变且只求和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2020/12052563
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！