Medium

题目描述

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

示例 2：

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

提示：

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

解题思路

这道题要求计算矩阵中每个位置的邻域和，邻域范围由参数 k 决定。

朴素解法：对于每个位置 (i,j)，直接遍历其 (2k+1) × (2k+1) 的邻域范围，累加有效位置的值。时间复杂度为 O(mnk²)。

前缀和优化（推荐）：使用二维前缀和来快速计算矩形区域和。核心思路是：

  1. 构建前缀和数组 prefix，其中 prefix[i][j] 表示从 (0,0) 到 (i-1,j-1) 矩形区域的元素和
  2. 利用容斥原理，任意矩形 (r1,c1) 到 (r2,c2) 的区域和可以通过前缀和快速计算： sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
  3. 对于位置 (i,j)，其邻域范围为 [max(0,i-k), min(m-1,i+k)] × [max(0,j-k), min(n-1,j+k)]

前缀和方法将单次区域和查询的复杂度从 O(k²) 降至 O(1)，总时间复杂度为 O(mn)。

需要注意边界处理，确保计算的矩形范围不超出原矩阵边界。

代码实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        
        // 构建前缀和数组，大小为 (m+1) x (n+1)
        vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + 
                              prefix[i][j-1] - prefix[i-1][j-1];
            }
        }
        
        vector<vector<int>> result(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int r1 = max(0, i - k);
                int c1 = max(0, j - k);
                int r2 = min(m - 1, i + k);
                int c2 = min(n - 1, j + k);
                
                result[i][j] = prefix[r2+1][c2+1] - prefix[r1][c2+1] - 
                              prefix[r2+1][c1] + prefix[r1][c1];
            }
        }
        
        return result;
    }
};

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        
        # 构建前缀和数组，大小为 (m+1) x (n+1)
        prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefix[i][j] = (mat[i-1][j-1] + prefix[i-1][j] + 
                               prefix[i][j-1] - prefix[i-1][j-1])
        
        result = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r1 = max(0, i - k)
                c1 = max(0, j - k)
                r2 = min(m - 1, i + k)
                c2 = min(n - 1, j + k)
                
                result[i][j] = (prefix[r2+1][c2+1] - prefix[r1][c2+1] - 
                               prefix[r2+1][c1] + prefix[r1][c1])
        
        return result

public class Solution {
    public int[][] MatrixBlockSum(int[][] mat, int k) {
        int m = mat.Length, n = mat[0].Length;
        
        // 构建前缀和数组，大小为 (m+1) x (n+1)
        int[,] prefix = new int[m + 1, n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i, j] = mat[i-1][j-1] + prefix[i-1, j] + 
                              prefix[i, j-1] - prefix[i-1, j-1];
            }
        }
        
        int[][] result = new int[m][];
        for (int i = 0; i < m; i++) {
            result[i] = new int[n];
            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);
                
                result[i][j] = prefix[r2+1, c2+1] - prefix[r1, c2+1] - 
                              prefix[r2+1, c1] + prefix[r1, c1];
            }
        }
        
        return result;
    }
}

var matrixBlockSum = function(mat, k) {
    const m = mat.length, n = mat[0].length;
    
    // 构建前缀和数组，大小为 (m+1) x (n+1)
    const prefix = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + 
                          prefix[i][j-1] - prefix[i-1][j-1];
        }
    }
    
    const result = Array(m).fill().map(() => Array(n));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const r1 = Math.max(0, i - k);
            const c1 = Math.max(0, j - k);
            const r2 = Math.min(m - 1, i + k);
            const c2 = Math.min(n - 1, j + k);
            
            result[i][j] = prefix[r2+1][c2+1] - prefix[r1][c2+1] - 
                          prefix[r2+1][c1] + prefix[r1][c1];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型前缀和解法朴素解法
时间复杂度O(mn)O(mnk²)
空间复杂度O(mn)O(1)

相关题目