子矩阵元素加 1

You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes.

You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation:

• Add 1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). That is, add 1 to mat[x][y] for all row1i <= x <= row2i and col1i <= y <= col2i.

Return the matrix mat after performing every query.

 

Example 1:

Input: n = 3, queries = [[1,1,2,2],[0,0,1,1]]
Output: [[1,1,0],[1,2,1],[0,1,1]]
Explanation: The diagram above shows the initial matrix, the matrix after the first query, and the matrix after the second query.
- In the first query, we add 1 to every element in the submatrix with the top left corner (1, 1) and bottom right corner (2, 2).
- In the second query, we add 1 to every element in the submatrix with the top left corner (0, 0) and bottom right corner (1, 1).

Example 2:

Input: n = 2, queries = [[0,0,1,1]]
Output: [[1,1],[1,1]]
Explanation: The diagram above shows the initial matrix and the matrix after the first query.
- In the first query we add 1 to every element in the matrix.

 

Constraints:

• 1 <= n <= 500
• 1 <= queries.length <= 104
• 0 <= row1i <= row2i < n
• 0 <= col1i <= col2i < n

/*
 * 思路：
 * 1. 初始化一个 n x n 的矩阵 mat，全部元素设为 0。
 * 2. 使用 Java Stream 对每一个 query 进行处理。
 * 3. 对于每一个 query，通过 stream 遍历其指定的子矩阵区域，将该区域内的每个元素加 1。
 * 4. 返回最终的矩阵 mat。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int[][] rangeAddQueries(int n, int[][] queries) {
        int[][] mat = new int[n][n];
        Arrays.stream(queries).forEach(query -> {
            int row1 = query[0];
            int col1 = query[1];
            int row2 = query[2];
            int col2 = query[3];
            IntStream.rangeClosed(row1, row2).forEach(i -> 
                IntStream.rangeClosed(col1, col2).forEach(j -> mat[i][j]++)
            );
        });
        return mat;
    }
}

此题解使用了二维差分数组的方法来高效处理范围加法问题。首先，创建一个 (n+2)x(n+2) 的差分数组 diff，初始化所有值为0。对于每个查询，使用差分数组的性质，通过更新矩阵的四个关键点来表示子矩阵内所有元素增加1的操作。这四个点是：左上角、右上角+1、左下角+1和右下角+1+1。最后，通过计算二维前缀和来还原出最终的矩阵，这样避免了直接对每个子矩阵内的每个元素进行迭代更新，从而提高效率。

O(n^2)

O(n^2)