【LeetCode每日一题】二维前缀和基本概念与案例

二维前缀和

根据某个块块 的 左上角坐标，和右下角坐标 求出 块块的累加和。

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

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {

    let row = matrix.length;
    let col = matrix[0].length;

    // 初始化一个二维数组，用来存储每个位置的累加和。
    let sum = new Array(row+1).fill(0);
    for(let i = 0; i < sum.length; i++){
        sum[i] = new Array(col+1).fill(0);
    }

    for(let i = 1; i <= row; i++){
        for(let j = 1; j <= col; j++){
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
        }
    }

    this.sum = sum;
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
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];
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */

例题：

给定一个M×N的矩阵，矩阵上每个数字代表一个区域内有多少个传感器，给定一个CNT×CNT大小的窗口，统计每个窗口内传感器的总数

需要统计在M×N矩阵中，窗口内传感器总数最大的所有窗口，并统计所有的窗口中总共有多少种不同的数字。

1. 遍历一次二维数组，记录二维数组的前缀和。记录为preSum
2. 遍历preSum，从 i :cnt → len,j:cnt → len ,计算每个小窗口的区间和。记录为cntSum
3. 最后遍历cntSum数组，找到最大的窗口，并且用set记录窗口的数字总量。

const SensorsNumCategory = (sensors,cnt) => {

    // 构造二维前缀和数组
    let preSumArr = new Array(sensors.length+1);
    let len = sensors[0].length;
    for(let i = 0; i < sensors.length+1; i++){
        preSumArr[i] = new Array(len+1).fill(0);
    }

    for(let i = 1; i < preSumArr.length; i++){
        for(let j = 1;j < preSumArr[i].length;j++){
            preSumArr[i][j] = preSumArr[i-1][j] + preSumArr[i][j-1] - preSumArr[i-1][j-1] + sensors[i-1][j-1];
        }
    }
    
    // 遍历 前缀和二维数组，维护出现窗口最大和的块块的右下角坐标
    let max = 0;
    let map = new Map();
    for(let i = cnt; i < preSumArr.length; i++){
        for(let j = cnt; j < preSumArr[i].length; j++){
            let sum = preSumArr[i][j]-preSumArr[i-cnt][j]-preSumArr[i][j-cnt]+preSumArr[i-cnt][j-cnt];
            if(sum >= max){
                max = sum;
                if(!map.has(max)){
                    map.set(max,[])
                }
                map.get(max).push([i,j])
            }
        }
    }

    let arr = map.get(max);
    let res = [];

    for(let i = 0; i < arr.length; i++){
        [x,y] = arr[i];
        res.push(...getElem([x-cnt,y-cnt],cnt,sensors));
    }
 // 对数组元素进行去重
    return Array.from(new Set(res));
}

// 根据右下角坐标获取块块里的所有元素
const getElem = (arr,cnt,sensors) => {
    let res = [];
    for(let i = arr[0]; i < arr[0]+cnt; i++){
        for(let j = arr[1]; j < arr[1]+cnt; j++){
            res.push(sensors[i][j])
        }
    }
    return res;
}
console.log(SensorsNumCategory([[1,3,4], [3,2,5],[1,6,1]],2))