Medium

题目描述

给你一个正整数 n，表示最初有一个 n x n 大小的、下标从 0 开始的整数矩阵 mat，矩阵元素均为 0。

另给你一个二维整数数组 queries。对于每个查询 queries[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 <= 500
  • 1 <= queries.length <= 10^4
  • 0 <= row1i <= row2i < n
  • 0 <= col1i <= col2i < n

解题思路

这道题要求我们对子矩阵进行区间更新操作，如果直接模拟每次查询都去更新整个子矩阵，时间复杂度会很高。我们可以使用二维差分数组的思想来优化。

核心思路是：

  1. 差分数组思想：对于一维数组的区间加法，我们可以在区间起点+1，区间终点后一位-1，最后做前缀和恢复原数组
  2. 二维扩展：对于二维矩阵，我们需要处理每一行。对于查询[row1, col1, row2, col2]，我们在第row1到row2行的每一行中，在第col1列+1，在第col2+1列-1
  3. 前缀和还原：所有查询处理完毕后，对每一行进行前缀和计算，得到最终结果

具体步骤：

  • 创建一个(n+1) x (n+1)的差分数组，多一列是为了方便处理边界
  • 对于每个查询，在受影响的每一行中标记差分值
  • 最后对每一行计算前缀和，得到最终的增量矩阵

时间复杂度从朴素的O(queries × n²)优化到O(queries × n + n²)。

代码实现

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> diff(n, vector<int>(n + 1, 0));
        
        // 处理所有查询，构建差分数组
        for (auto& query : queries) {
            int row1 = query[0], col1 = query[1];
            int row2 = query[2], col2 = query[3];
            
            for (int i = row1; i <= row2; i++) {
                diff[i][col1]++;
                diff[i][col2 + 1]--;
            }
        }
        
        // 对每一行计算前缀和，得到最终结果
        vector<vector<int>> result(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = result[i][j-1] + diff[i][j];
            }
        }
        
        return result;
    }
};

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        # 创建差分数组，多一列方便处理边界
        diff = [[0] * (n + 1) for _ in range(n)]
        
        # 处理所有查询
        for row1, col1, row2, col2 in queries:
            for i in range(row1, row2 + 1):
                diff[i][col1] += 1
                diff[i][col2 + 1] -= 1
        
        # 计算前缀和得到最终结果
        result = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                result[i][j] = result[i][j-1] + diff[i][j]
        
        return result

public class Solution {
    public int[][] RangeAddQueries(int n, int[][] queries) {
        // 创建差分数组
        int[][] diff = new int[n][];
        for (int i = 0; i < n; i++) {
            diff[i] = new int[n + 1];
        }
        
        // 处理所有查询
        foreach (var query in queries) {
            int row1 = query[0], col1 = query[1];
            int row2 = query[2], col2 = query[3];
            
            for (int i = row1; i <= row2; i++) {
                diff[i][col1]++;
                diff[i][col2 + 1]--;
            }
        }
        
        // 计算前缀和得到最终结果
        int[][] result = new int[n][];
        for (int i = 0; i < n; i++) {
            result[i] = new int[n];
            for (int j = 0; j < n; j++) {
                result[i][j] = (j > 0 ? result[i][j-1] : 0) + diff[i][j];
            }
        }
        
        return result;
    }
}

var rangeAddQueries = function(n, queries) {
    // 创建差分数组
    const diff = Array(n).fill().map(() => Array(n + 1).fill(0));
    
    // 处理所有查询
    for (const [row1, col1, row2, col2] of queries) {
        for (let i = row1; i <= row2; i++) {
            diff[i][col1]++;
            diff[i][col2 + 1]--;
        }
    }
    
    // 计算前缀和得到最终结果
    const result = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            result[i][j] = (j > 0 ? result[i][j-1] : 0) + diff[i][j];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(queries × n + n²)
空间复杂度O(n²)
  • 时间复杂度：处理queries需要O(queries × n)时间，计算前缀和需要O(n²)时间
  • 空间复杂度：需要额外的差分数组空间O(n²)，结果数组不计入额外空间

相关题目