LeetCode 1314. 矩阵区域和

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

题目描述

✅ 1314. 矩阵区域和

题意分析

给定 m × n 的整数矩阵 mat 和一个整数 k，要构造同样大小的矩阵 answer，其中 answer[i][j] 等于所有满足 i-k <= r <= i+k 且 j-k <= c <= j+k 且 (r, c) 落在矩阵内的 mat[r][c] 之和。

换句话说，每个位置的答案是以它为中心、边长 2k+1 的正方形窗口内所有元素的和，窗口越界的部分直接裁掉而不是补零——注意「裁掉」和「补零」在求和上结果相同，但在写下标时完全不同，前者要把边界钳位到矩阵内，后者会直接越界访问。

题目的结构特征是：同一个矩阵上要做 m × n 次矩形区域求和，矩阵本身自始至终不变。查询次数等于格子数，而每次查询的窗口面积可达 $(2k+1)^2$，这是典型的「大量只读区间查询」，强烈提示应该先做一次预处理，把单次查询压到常数时间。

约束里 m, n 可达 100、k 可达 100。k 允许大于矩阵边长，此时每个窗口都会覆盖整个矩阵，所有答案相同——这个极端情况必须靠钳位自然处理，不能假设 i + k < m。元素取值在 [1, 100]，全为正数且总和最大 100 × 100 × 100 = 10^6，int 完全够用，不必担心溢出。

边界要留意四点：k 可能为 0，此时 answer 就是 mat 本身；窗口的四个边都可能越界，上下左右要分别钳位；答案矩阵与输入同形，不是 (m+1) × (n+1)；窗口是闭区间，两端都要取到。

解法：二维前缀和

核心思路

每个答案都是原矩阵上的矩形区域和，而且矩阵在查询期间不变。若逐格扫描窗口，相邻窗口会重复计算大量元素；二维前缀和可以把每次矩形求和降为 $O(1)$。

定义 prefix[i][j] 为原矩阵前 i 行、前 j 列的元素和。第 0 行和第 0 列表示空区域，均为 0。递推使用容斥：

prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + mat[i-1][j-1]。

构造不变量：计算 prefix[i][j] 时，它依赖的上方、左侧和左上三格都已经完成，所以该格始终准确表示对应左上矩形之和。

对原矩阵闭区间 [row1, row2] × [col1, col2]，区域和为：

prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]。

两个减项移除窗口上方和左侧区域，左上重叠部分被减了两次，所以最后加回一次。每个中心 (i, j) 的四条边分别钳位到矩阵范围，再代入同一公式。

正确性：前缀递推由容斥准确覆盖每个左上矩形；查询公式又从右下大矩形中精确保留目标区域。因此每个 answer[i][j] 都等于题目规定的裁剪窗口和。

解题步骤

  1. 创建 (rows + 1) × (cols + 1) 的 prefix，按行列递增构造二维前缀和。
  2. 对每个位置 (i, j)，计算并钳位 row1、row2、col1、col2。
  3. 用四项容斥公式求窗口和并写入同尺寸结果矩阵。

对 mat = [[1,2,3],[4,5,6],[7,8,9]]、k = 1，中心 (1,1) 的窗口覆盖整个矩阵，结果为 45；右下角 (2,2) 的窗口为 [[5,6],[8,9]]，结果为 28。

k = 0 时四条边都等于当前位置，结果就是原矩阵的值；k 大于行列数时，钳位后每个窗口都覆盖整个矩阵；非方阵必须分别使用 rows 和 cols 处理上下界。

代码实现

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(1)$。
  • 空间复杂度：$O(mn)$，用于二维前缀和；结果矩阵不计入额外空间。

关键点总结

  • 静态矩阵上的大量区域求和，优先考虑二维前缀和。
  • 第 0 行、第 0 列哨兵统一了构造与查询边界。
  • 矩形查询必须“减上、减左、加回左上重叠”。
  • 窗口四条边要独立钳位，尤其不能把行数与列数混用。

易错点总结

  • 漏掉左上补偿项：内部窗口会把左上区域多减一次，例如样例右下窗口会得到 27 而不是 28。
  • 右下坐标忘记加 1：prefix 下标表示行列数量，闭区间右下角必须转换为 row2 + 1、col2 + 1。
  • 只钳位部分边界：k 可以大于矩阵尺寸，四条边都可能越界。
  • 行列上界写反：非方阵上应分别使用 rows - 1 与 cols - 1。
  • 把前缀数组开成原矩阵大小：会失去空行空列哨兵并引入大量边界分支。

相似题目

题目 难度 考察点
303. 区域和检索 - 数组不可变 简单 一维版模板，先在这里把「下标是计数」的偏移想透
304. 二维区域和检索 - 矩阵不可变 中等 同款容斥，区别只是查询区间由调用方给定而非由中心点推出
308. 二维区域和检索 - 矩阵可修改 中等 矩阵可改导致前缀失效，需要二维树状数组同时支持更新与查询
1292. 元素和小于等于阈值的正方形的最大边长 中等 在前缀和之上再套一层对边长的二分，利用「边长越大和越大」的单调性
1074. 元素和为目标值的子矩阵数量 困难 枚举上下行界压成一维，再用哈希表做前缀和配对计数
363. 矩形区域不超过 K 的最大数值和 困难 压成一维后要在有序集合里找最小的不小于某值的前缀，需要平衡树而非哈希
221. 最大正方形 中等 用动态规划递推边长比前缀和更直接，状态是「以该格为右下角的最大边长」
1277. 统计全为 1 的正方形子矩阵 中等 与 221 同一递推式，但把最大值改成累加，体现「边长即方案数」
85. 最大矩形 困难 逐行压成柱状图后套单调栈，说明矩形类问题不是只有前缀和一条路
面试题 17.24. 最大子矩阵 困难 枚举行界 + 一维最大子段和，还要额外记录四个边界坐标
1109. 航班预订统计 中等 差分数组是前缀和的逆过程，适合「区间批量加、最后统一查」
370. 区间加法 中等 一维差分模板，与本题构成「先改后查」与「只查不改」的对照
LCR 013. 二维区域和检索 - 矩阵不可变 中等 与 304 同题，适合把容斥公式再默写一遍