LeetCode 题解工作台
子矩阵元素加 1
给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。 另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1 i , col1 i , row2 i , col2 i ] ，请你执行下述操作： 找出 左上角 为 …
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
二维差分数组是一种用于高效处理二维数组区间更新的技巧。我们可以通过维护一个与原矩阵大小相同的差分矩阵来实现对子矩阵的快速更新。 假设我们有一个二维差分矩阵 ，初始时所有元素均为 。对于每个查询 $[\textit{row1}, \textit{col1}, \textit{row2}, \textit{col2}]$，我们可以通过以下步骤更新差分矩阵：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。
另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：
- 找出 左上角 为
(row1i, col1i)且 右下角 为(row2i, col2i)的子矩阵，将子矩阵中的 每个元素 加1。也就是给所有满足row1i <= x <= row2i和col1i <= y <= col2i的mat[x][y]加1。
返回执行完所有操作后得到的矩阵 mat 。
示例 1：
输入：n = 3, queries = [[1,1,2,2],[0,0,1,1]] 输出：[[1,1,0],[1,2,1],[0,1,1]] 解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。 - 第一个操作：将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。 - 第二个操作：将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。
示例 2：
输入：n = 2, queries = [[0,0,1,1]] 输出：[[1,1],[1,1]] 解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵。 - 第一个操作：将矩阵中的每个元素加 1 。
提示：
1 <= n <= 5001 <= queries.length <= 1040 <= row1i <= row2i < n0 <= col1i <= col2i < n
解题思路
方法一：二维差分
二维差分数组是一种用于高效处理二维数组区间更新的技巧。我们可以通过维护一个与原矩阵大小相同的差分矩阵来实现对子矩阵的快速更新。
假设我们有一个二维差分矩阵 ，初始时所有元素均为 。对于每个查询 ，我们可以通过以下步骤更新差分矩阵：
- 在位置 加 。
- 在位置 减 ，前提是 。
- 在位置 减 ，前提是 。
- 在位置 加 ，前提是 且 。
完成所有查询后，我们需要通过前缀和的方式将差分矩阵转换回原矩阵。即，对于每个位置 ，我们计算：
时间复杂度 ，其中 和 分别是 的长度和给定的 。忽略答案的空间消耗，空间复杂度 。
class Solution:
def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
mat = [[0] * n for _ in range(n)]
for x1, y1, x2, y2 in queries:
mat[x1][y1] += 1
if x2 + 1 < n:
mat[x2 + 1][y1] -= 1
if y2 + 1 < n:
mat[x1][y2 + 1] -= 1
if x2 + 1 < n and y2 + 1 < n:
mat[x2 + 1][y2 + 1] += 1
for i in range(n):
for j in range(n):
if i:
mat[i][j] += mat[i - 1][j]
if j:
mat[i][j] += mat[i][j - 1]
if i and j:
mat[i][j] -= mat[i - 1][j - 1]
return mat
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * q) using the row-wise prefix sum method, where q is the number of queries, compared to O(q * n^2) for naive updates. Space complexity is O(n^2) for the matrix plus O(n) extra for row differences. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks about handling multiple overlapping submatrices efficiently.
- question_mark
Mentions optimizing from naive element-wise updates to prefix sum techniques.
- question_mark
Checks understanding of Array plus Matrix patterns and row-level operations.
常见陷阱
外企场景- error
Trying to increment all elements directly for each query, causing TLE for large n.
- error
Forgetting to apply prefix sums after row-wise difference updates.
- error
Confusing row and column indices when applying submatrix increments.
进阶变体
外企场景- arrow_right_alt
Increment submatrices with arbitrary values instead of one.
- arrow_right_alt
Apply similar updates on non-square matrices or rectangular grids.
- arrow_right_alt
Count how many times each cell exceeds a threshold after multiple queries.