讲讲 LC 2536 给子矩阵局部增加 1动态规划
kikicat
2536. 给子矩阵局部增加 1
题目在讲什么
给你一个整数
n,一开始有个
n × n的全零矩阵。再给你一堆查询,每个查询是
[row1, col1, row2, col2],表示一个子矩阵的左上角和右下角。对于每个查询,你要把这个子矩阵里的每个格子都加 1。所有查询做完后,返回最终的矩阵。
举个例子:
n = 3,查询
[[1,1,2,2]],意思是把左上角
(1,1)、右下角
(2,2)围起来的那块区域整体加 1,结果是:
0 0 0
0 1 1
0 1 1
最直接的做法(会超时)
对每个查询,老老实实用两层循环遍历那块子矩阵,每个格子
+1。这样每个查询最坏要遍历整个
n × n,如果查询有
q个,总复杂度是
O(q · n²)。数据一大就慢。
高效做法:二维差分数组
核心思路是先只在四个角上做标记,最后再一次性把整张矩阵"还原"出来。
先理解一维差分
假设有个数组,你想给区间
[l, r]里每个数都
+1。与其一个个加,你可以只做两步:
diff[l] += 1 # 从 l 开始"打开开关"
diff[r+1] -= 1 # 到 r+1 处"关掉开关"
最后对
diff求一遍前缀和,
[l, r]这段就自动都变成 1 了。因为前缀和会把
+1从
l一路累加下去,而
r+1的
-1正好把后面的抵消掉。
推广到二维
二维前缀和的特点是:每个格子会累加它左上方所有格子的值。所以如果你只在
(r1, c1)标一个
+1,那么求前缀和之后,从这个点开始往右下方无限延伸的整片区域都会
+1。
我们不想让它无限延伸,只想框住那个子矩阵,所以要在边界上"止损":
diff[r1][c1] += 1 # 从左上角开始加
diff[r2+1][c1] -= 1 # 把"往下超出去"的部分砍掉
diff[r1][c2+1] -= 1 # 把"往右超出去"的部分砍掉
diff[r2+1][c2+1] += 1 # 右下角被砍了两次,补回来一次
最后那个
+1是因为右下角那块区域同时被下面和右边两个
-1减了两遍,要加回来一次(容斥原理)。
为了避免
r2+1或
c2+1越界,把
diff开成
(n+1) × (n+1)就行。
还原矩阵
所有查询都标记完之后,对
diff求二维前缀和,得到的就是答案:
mat[j] = diff[j] + mat[i-1][j] + mat[j-1] - mat[i-1][j-1]
代码
def rangeAddQueries(n, queries):
# 多开一圈,防止 r2+1 / c2+1 越界
diff = [[0] * (n + 1) for _ in range(n + 1)]
# 每个查询只动四个角
for r1, c1, r2, c2 in queries:
diff[r1][c1] += 1
diff[r2 + 1][c1] -= 1
diff[r1][c2 + 1] -= 1
diff[r2 + 1][c2 + 1] += 1
# 二维前缀和还原
mat = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
top = mat[i - 1][j] if i > 0 else 0
left = mat[j - 1] if j > 0 else 0
topleft = mat[i - 1][j - 1] if i > 0 and j > 0 else 0
mat[j] = diff[j] + top + left - topleft
return mat
复杂度
求加米！
题目在讲什么
给你一个整数
n,一开始有个
n × n的全零矩阵。再给你一堆查询,每个查询是
[row1, col1, row2, col2],表示一个子矩阵的左上角和右下角。对于每个查询,你要把这个子矩阵里的每个格子都加 1。所有查询做完后,返回最终的矩阵。
举个例子:
n = 3,查询
[[1,1,2,2]],意思是把左上角
(1,1)、右下角
(2,2)围起来的那块区域整体加 1,结果是:
0 0 0
0 1 1
0 1 1
最直接的做法(会超时)
对每个查询,老老实实用两层循环遍历那块子矩阵,每个格子
+1。这样每个查询最坏要遍历整个
n × n,如果查询有
q个,总复杂度是
O(q · n²)。数据一大就慢。
高效做法:二维差分数组
核心思路是先只在四个角上做标记,最后再一次性把整张矩阵"还原"出来。
先理解一维差分
假设有个数组,你想给区间
[l, r]里每个数都
+1。与其一个个加,你可以只做两步:
diff[l] += 1 # 从 l 开始"打开开关"
diff[r+1] -= 1 # 到 r+1 处"关掉开关"
最后对
diff求一遍前缀和,
[l, r]这段就自动都变成 1 了。因为前缀和会把
+1从
l一路累加下去,而
r+1的
-1正好把后面的抵消掉。
推广到二维
二维前缀和的特点是:每个格子会累加它左上方所有格子的值。所以如果你只在
(r1, c1)标一个
+1,那么求前缀和之后,从这个点开始往右下方无限延伸的整片区域都会
+1。
我们不想让它无限延伸,只想框住那个子矩阵,所以要在边界上"止损":
diff[r1][c1] += 1 # 从左上角开始加
diff[r2+1][c1] -= 1 # 把"往下超出去"的部分砍掉
diff[r1][c2+1] -= 1 # 把"往右超出去"的部分砍掉
diff[r2+1][c2+1] += 1 # 右下角被砍了两次,补回来一次
最后那个
+1是因为右下角那块区域同时被下面和右边两个
-1减了两遍,要加回来一次(容斥原理)。
为了避免
r2+1或
c2+1越界,把
diff开成
(n+1) × (n+1)就行。
还原矩阵
所有查询都标记完之后,对
diff求二维前缀和,得到的就是答案:
mat[j] = diff[j] + mat[i-1][j] + mat[j-1] - mat[i-1][j-1]
代码
def rangeAddQueries(n, queries):
# 多开一圈,防止 r2+1 / c2+1 越界
diff = [[0] * (n + 1) for _ in range(n + 1)]
# 每个查询只动四个角
for r1, c1, r2, c2 in queries:
diff[r1][c1] += 1
diff[r2 + 1][c1] -= 1
diff[r1][c2 + 1] -= 1
diff[r2 + 1][c2 + 1] += 1
# 二维前缀和还原
mat = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
top = mat[i - 1][j] if i > 0 else 0
left = mat[j - 1] if j > 0 else 0
topleft = mat[i - 1][j - 1] if i > 0 and j > 0 else 0
mat[j] = diff[j] + top + left - topleft
return mat
复杂度
- 时间:标记每个查询是O(1),一共O(q);最后还原是O(n²)。总共O(q + n²),比暴力的O(q · n²)快很多。
- 空间:O(n²),用来存差分和结果矩阵。
求加米！
共3条回复
✨ 您正在体验新版论坛UI
