2536. Increment Submatrices by One

Leetcode link

题目简介

/**
 * @param {number} n
 * @param {number[][]} queries
 * @return {number[][]}
 */

本题给我们一个数字 n 代表一个 n*n 的矩阵，初始元素都是 0

还有一个二位数组 queries ，数组的每一项都是 [row1, col1, row2, col2] 代表我们要查询的矩阵范围

如果某个矩阵元素被查询到了，我们需要把该元素 +1

最后需要返回矩阵经过所有查询后的结果

解题思路——模拟

这题可以直接模拟，需要三层循环

Javascript

/**
 * @param {number} n
 * @param {number[][]} queries
 * @return {number[][]}
 */
var rangeAddQueries = function (n, queries) {
    const matrix = Array.from({ length: n }, _ => new Array(n).fill(0))

    for (const [r1, c1, r2, c2] of queries) {
        for (let i = r1; i <= r2; i++) {
            for (let j = c1; j <= c2; j++) {
                matrix[i][j]++
            }
        }
    }

    return matrix
};

解题思路——辅助矩阵

如果想要减少时间复杂度，我们可以用一个辅助矩阵来帮助我们

如果这个辅助矩阵可以帮我们确定所有 query 的范围，我们后续只需要一次双层遍历就可以完成矩阵更新的操作

假设我们有：n = 3, queries = [[1,1,2,2]]

我们的预期结果是：

0 0 0
0 1 1
0 1 1

我们可以构建一个辅助矩阵 helperMatrix 来划分范围：

0 0 0 0
0 1 0 -1
0 0 0 0
0 -1 0 0

我们给辅助函数加了一行跟一列，这样一来我们可以用来标记 query 的范围边界

有了这个辅助函数，我们在处理矩阵第 1 行与第 1 列的时候只要把 1～-1 之间的元素加一即可：

0 0 0
0 1 1
0 1 x

现在我们要来处理第 3 行第 3 列的 x，x 的值只跟 4 个因素有关：

1. 其左边元素的值
2. 其上方元素的值
3. 其左上方元素的值
4. 辅助矩阵 helperMatrix 对应位置的值

具体公式为：辅助矩阵 helperMatrix 对应位置的值 + 其左边元素的值 + 其上方元素的值 - 其左上方元素的值

最后，我们还需要考虑 x 右下方的矩阵元素的值（如果有的话），我们需要把 x 右下角的位置加一

最后我们的辅助矩阵 helperMatrix 变成了：

0 0 0 0
0 1 0 -1
0 0 0 0
0 -1 0 1

Javascript

/**
 * @param {number} n
 * @param {number[][]} queries
 * @return {number[][]}
 */
var rangeAddQueries = function (n, queries) {
    const helperMatrix = Array.from({ length: n + 1 }, _ => new Array(n + 1).fill(0))
    for (const [r1, c1, r2, c2] of queries) {
        helperMatrix[r1][c1]++
        helperMatrix[r1][c2 + 1]--
        helperMatrix[r2 + 1][c1]--
        helperMatrix[r2 + 1][c2 + 1]++
    }

    const matrix = Array.from({ length: n }, _ => new Array(n).fill(0))
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const upper = i === 0 ? 0 : matrix[i - 1][j]
            const left = j === 0 ? 0 : matrix[i][j - 1]
            const upperLeft = i === 0 || j === 0 ? 0 : matrix[i - 1][j - 1]
            matrix[i][j] = helperMatrix[i][j] + upper + left - upperLeft
        }
    }

    return matrix
};