跳到主要内容

区域题库

矩阵区域和​

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

方案 二位前缀和​

思路:

  • 通过sums表示数组matrix的二维前缀和，sums的维数为(row+1)*(col+1)。其中sums[i][j]表示数组matrix中以(0,0)为左上角，(i-1,j-1)为右下角的矩形子数组的元素之和。方程为:sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+matrix[i-1][j-1]

  • 设sumsK为以(i-k,j-k)为左上角，(i+k,j+k)为右下角的矩形子数组的元素之和，方程为:sumsK=sums[i+k+1][j+k+1]-sums[i-k][j+k+1]-sums[i+k+1][j-k]+sums[i-k][j-k]

  • 确定边界范围: i+k+1、j+k+、i-k、j-k这些下标有可能不在矩阵内，因此对于所有的横坐标我们需要将其规范在[0,row]区间内；对于所有的纵坐标，我们需要将其规范在[0,col]区间内

    • x=max(min(x,row),0)

    • y=max(min(y,col),0)

function get(sums,row,col,x,y){
    x=Math.max(Math.min(x,row),0);
    y=Math.max(Math.min(y,col),0);
    return sums[x][y];
}
function matrixBlockSum(matrix, k) {
    const row=matrix.length;
    const col=matrix[0].length;
    const sums=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(0))
    for(let i=1;i<=row;i++){
        for(let j=1;j<=col;j++){
            sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+matrix[i-1][j-1];
        }
    }
    const result=new Array(row).fill(0).map(()=>new Array(col).fill(0));
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            result[i][j]=get(sums,row,col,i+k+1,j+k+1)-get(sums,row,col,i-k,j+k+1)-get(sums,row,col,i+k+1,j-k)+get(sums,row,col,i-k,j-k);
        }
    }
    return result;
};

性能分析:

  • 时间复杂度: O(MN)
  • 空间复杂度: O(MN)

区域和检索 - 数组不可变​

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例:

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

方案 前缀和​

思路: 设数组nums的长度为n,创建长度为n+1的前缀和数组sum,对于0<=i<n都有sum[i+1]=sum[i]+num[i]。

  • sum[i]=nums[0]+nums[1]+……+nums[i-1];

  • sum[i+1]=nums[0]+nums[1]+……+nums[i-1]+nums[i];

  • sumRange[i,j]=sum[j+1]-sum[i]

function NumArray(nums) {
    const len=nums.length;
    this.sum=new Array(len+1).fill(0);
    for(let i=0;i<len;i++){
        this.sum[i+1]=this.sum[i]+nums[i];
    }
};

NumArray.prototype.sumRange = function(left, right) {
    return this.sum[right+1]-this.sum[left];
};

性能分析:

  • 时间复杂度: O(1)
  • 空间复杂度: O(n)

二维区域和检索 - 矩阵不可变​

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化

  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

示例1:

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

方案 前缀和​

思路: 设row和col分别是矩阵matrix的行数和列数.定义当0<=i<m且0<=j<n时,sum[i,j]为矩阵matrix的以(i,j)为右下角的子矩阵的元素之和:

  • sum[i,j]=sum[i-1,j]+sum[i,j-1]-sum[i-1,j-1]+matrix[i-1][j-1];

  • sum[i+1,j+1]=sum[i,j+1]+sum[i+1,j]-sum[i,j]+matrix[i][j];

  • sumRange(row1,col1,row2,col2)=sum[row2+1,col2+1]-sum[row1,col2+1]-sum[row2+1][col1]+sum[row1][col1];

function NumMatrix(matrix) {
    const row=matrix.length;
    if(row<=0){
        return 
    }
    const col=matrix[0].length;
    this.sum=new Array(row+1).fill(0).map(()=>new Array(col+1).fill(0));
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            this.sum[i+1][j+1]=this.sum[i][j+1]+this.sum[i+1][j]-this.sum[i][j]+matrix[i][j];
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    return this.sum[row2+1][col2+1]-this.sum[row1][col2+1]-this.sum[row2+1][col1]+this.sum[row1][col1];
};

性能分析:

  • 时间复杂度: O(mn)
  • 空间复杂度: O(mn)