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

二维前缀和

图片来源：https://leetcode.cn/circle/discuss/UUuRex/[添加链接描述]
在这里插入图片描述

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

在这里插入图片描述

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矩阵中，窗口内传感器总数最大的所有窗口，并统计所有的窗口中总共有多少种不同的数字。

遍历一次二维数组，记录二维数组的前缀和。记录为preSum
遍历preSum，从 i :cnt → len,j:cnt → len ,计算每个小窗口的区间和。记录为cntSum
最后遍历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))