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
题目大概意思就是输入一个n表示n x n的矩阵，并输入一个queries的数组
queries = [[r1,c1,r2,c2],[...]]
其中每一个queries[i] 有四个元素
(r1,c1)为坐标，矩形的左上角
(r2,c2)为坐标，矩形的右下角
--------------------------------
然后queries[i]圈定的矩形对应的值加1
所以n x n的矩形中由queries圈定多个矩形，不同矩形重叠部分会叠加1.
思路1：
直接暴力算法，对queries中表示的矩形遍历矩形索引 并加1。
思路2:
思路主要是解决该问题：是针对其中一个位置，值应该是多少，可以一次算出来吗？
答案是可以的
针对某个位置(r,c)， 该位置的值如果被n个矩形圈定则值为n。
而位置(r,c) 被哪些矩形圈定可以通过(r-1, c) 和 (r, c-1)描述
可以这么处理：
(r-1, c)传递了该信息：被r-1上面出现的过的矩形圈定。
(r, c-1)传递了该信息：被当前行r出现过的矩形圈定。
所以对于matrix[r][c] += matrix[r-1][c] + matrix[r][c-1]
这里有个前提是matrix[r][c-1]还未更新，只是初始化的时候的值，所以代码处理上会是这样
matrix[r][c] += matrix[r-1][c]
而 matrix[r][c] += matrix[r][c-1]部分在上次循环中处理。
难点：边界处理。
上述只能解决queries[i] = (x, y, 无穷大x, 无穷大y)的情况
而不能处理有边界的情况，边界处理的方式有一个非常trick的方案:
直接在矩形外赋值为-1，套入上述公式时就能完美处理。。
比如
1 1 1 1 0 1 0 0 0 -1
1 1 1 1 0 ---> 0 0 0 0 0
1 1 1 1 0 ---> 0 0 0 0 0
0 0 0 0 0 -1 0 0 0 1
func rangeAddQueries(n int, queries [][]int) [][]int {
res := make([][]int, n)
for i := 0; i < n; i++ {
line := make([]int, n)
res[i] = line
}
for _, query := range queries {
leftPointX,leftPointY := query[0], query[1]
rightPointX, rightPointY := query[2], query[3]
for row := leftPointX; row <= rightPointX; row++ {
for col := leftPointY; col <= rightPointY; col++ {
res[row][col]++
}
}
}
return res
}func rangeAddQueries(n int, queries [][]int) [][]int {
res := make([][]int, n)
for i := 0; i < n; i++ {
line := make([]int, n)
res[i] = line
}
for _, query := range queries {
r1, c1, r2, c2 := query[0], query[1], query[2], query[3]
res[r1][c1] += 1
if c2+1 < n {
res[r1][c2+1] += -1
}
if r2+1 < n {
res[r2+1][c1] += -1
}
if r2+1 < n && c2+1 < n {
res[r2+1][c2+1] += 1
}
}
for r := 0; r < n; r++ {
for c := 0; c < n; c++ {
if c+1 < n {
res[r][c+1] += res[r][c]
}
if r-1 >= 0 {
res[r][c] += res[r-1][c]
}
}
}
return res
}