题目 #

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 [y] for 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 <= 10^4$
• 0 <= row1i <= row2i < n
• 0 <= col1i <= col2i < n

思路1 直接写 #

分析 #

• 据说会超时，不过我使用go好像处于C和python的中间状态，没有给超时

代码 #

 1func rangeAddQueries(n int, queries [][]int) [][]int {
 2	result := make([][]int, n)
 3	for i := range result {
 4		result[i] = make([]int, n)
 5	}
 6
 7	for _, v := range queries {
 8		for i := v[0]; i <= v[2]; i++ {
 9			for j := v[1]; j <= v[3]; j++ {
10				result[i][j]++
11			}
12		}
13	}
14	return result
15}

思路2 二维差分 #

分析 #

• 假设每一个query都是左上角到右下角，那么上面的时间复杂度就有点恐怖了
• 使用二维差分来做，每个元素影响自己右下角所有的点，那么query的左上就是1，右上就是-1，左下也是-1，右下就是1

query = [0, 0, 1, 1]

• 可以看出每个点的值都是包含自己的左上所有元素的和

• 那么可以得出每个点的值是 $自己 + 左邻居 + 上邻居 - 左上邻居$

代码 #

 1func rangeAddQueries1(n int, queries [][]int) [][]int {
 2	// 防止越界
 3	result := make([][]int, n+1)
 4	for i := range result {
 5		result[i] = make([]int, n+1)
 6	}
 7
 8	for _, v := range queries {
 9		r1, c1, r2, c2 := v[0], v[1], v[2]+1, v[3]+1
10		result[r1][c1] += 1
11		result[r1][c2] -= 1
12		result[r2][c1] -= 1
13		result[r2][c2] += 1
14	}
15
16	for i := range result {
17		result[i] = result[i][:n]
18		for j := range result[i] {
19			// 每个点都是其自身和左上所有元素的和
20			// 那么每个点都是自己+左邻居+上邻居-坐上邻居
21			add := 0
22			if i > 0 {
23				add += result[i-1][j]
24			}
25			if j > 0 {
26				add += result[i][j-1]
27			}
28			if i > 0 && j > 0 {
29				add -= result[i-1][j-1]
30			}
31			result[i][j] += add
32		}
33	}
34	return result[:n]
35}