1314. 矩阵区域和.md

• 1314. 矩阵区域和.md

• 动态规划 + 二维前缀和

/**
 *
 * @see 什么是二维前缀和 https://blog.csdn.net/qq_34990731/article/details/82807870
 * @see https://leetcode-cn.com/problems/matrix-block-sum/solution/you-qian-ru-shen-bao-li-xing-lie-qian-zh-5503/
 * @param {number[][]} mat
 * @param {number} k
 * @return {*}  {number[][]}
 */
function matrixBlockSum(mat: number[][], k: number): number[][] {

    const rows: number = mat.length,
        cols: number = mat[0].length,
        // 申请冗余的空间,这样就算的时候就无需判断越界的情况
        preSum: number[][] = new Array(rows + 1).fill(null).map(() => new Array(cols + 1).fill(0)); 

    for (let row = 1; row <= rows; ++row) {
        for (let col = 1; col <= cols; ++col) {
            preSum[row][col] = preSum[row][col - 1] + preSum[row - 1][col] - preSum[row - 1][col - 1] + mat[row - 1][col - 1];
        }
    }

    const results: number[][] = new Array(rows).fill(null).map(() => new Array(cols).fill(0));

    for (let row = 0; row < rows; ++row) {
        for (let col = 0; col < cols; ++col) {

            const startRow = Math.max(row - k, 0),
                endRow = Math.min(row + k, rows - 1),
                startCol = Math.max(col - k, 0),
                endCol = Math.min(col + k, cols - 1);

            results[row][col] = preSum[endRow + 1][endCol + 1] - (preSum[endRow + 1][startCol] + preSum[startRow][endCol + 1] - preSum[startRow][startCol]);
        }
    }

    return results;
};