LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.14
• 题目：2536.子矩阵元素加1
• 难度：中等
• 标签: 二维差分矩阵

1. 题目理解

问题描述：
给你一个正整数 n，表示最初有一个 n x n、下标从 0 开始的整数矩阵 mat，矩阵中填满了 0。另给你一个二维整数数组 queries，每个查询 query[i] = [row1i, col1i, row2i, col2i] 表示：找出左上角为 (row1i, col1i) 且右下角为 (row2i, col2i) 的子矩阵，将子矩阵中的每个元素加 1。返回执行完所有操作后得到的矩阵 mat。

示例：

输入：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. 解题思路

核心观察

• 暴力解法（直接遍历每个查询的子矩阵并逐元素加1）时间复杂度为 O(q×n²)（q 为查询数），当 n 和 q 较大时会超时。
• 二维差分矩阵的核心优势是将“区间加1”操作转化为4个点的标记，后续通过二维前缀和还原目标矩阵，时间复杂度骤降，是该类区间更新问题的最优解法。
• 差分矩阵需设计为 (n+2)×(n+2) 大小，避免处理 row2+1 或 col2+1 时数组越界，无需额外边界判断。

算法步骤

1. 初始化差分矩阵：创建 (n+2)×(n+2) 的二维数组 diff，初始值全为 0。
2. 处理每个查询：对每个查询 [r1, c1, r2, c2]，更新 diff 矩阵的4个关键位置：
   • diff[r1+1][c1+1]++：标记子矩阵左上角为增量起点；
   • diff[r1+1][c2+2]--：标记子矩阵右上角右侧，抵消该行后续列的增量；
   • diff[r2+2][c1+1]--：标记子矩阵左下角下方，抵消该列后续行的增量；
   • diff[r2+2][c2+2]++：标记子矩阵右下角右下方，抵消上述两次抵消的重叠区域。
3. 计算二维前缀和还原矩阵：对 diff 矩阵执行“先行后列”的二维前缀和计算，将差分标记的增量扩散到整个子矩阵，同时将结果存入目标矩阵 ans。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public static int[][] rangeAddQueries(int n, int[][] queries) {
        int[][] diff = new int[n + 2][n + 2];
        for (int[] q : queries) {
            int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
            diff[r1 + 1][c1 + 1]++;
            diff[r1 + 1][c2 + 2]--;
            diff[r2 + 2][c1 + 1]--;
            diff[r2 + 2][c2 + 2]++;
        }

        int[][] ans = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
                ans[i][j] = diff[i + 1][j + 1];
            }
        }
        return ans;
    }
}

4. 代码优化说明

• 下标转换优化：将原矩阵的 0-based 下标转为差分矩阵的 1-based 下标，避免处理 0 行 0 列的边界逻辑，简化代码。
• 原地前缀和计算：直接在差分矩阵 diff 上更新前缀和，无需额外开辟中间矩阵，空间复杂度优化至 O(n²)（仅差分矩阵和结果矩阵占用空间）。
• 无冗余操作：每个查询仅需4次赋值，前缀和计算仅需遍历 n×n 矩阵，全程无冗余循环，执行效率极高。

5. 复杂度分析

• 时间复杂度：O(q + n²)
  • 处理所有查询：O(q)，每个查询仅需4次数组更新；
  • 计算二维前缀和与构建结果矩阵：O(n²)，需遍历 n×n 规模的矩阵；
  • 整体复杂度不受查询中子矩阵大小影响，适合 n 和 q 较大的场景（如 n=1000、q=1e5）。
• 空间复杂度：O(n²)
  • 差分矩阵 diff 大小为 (n+2)×(n+2)，结果矩阵 ans 大小为 n×n，均为 O(n²) 级别，无额外冗余空间。

6. 总结

本题是二维差分矩阵的经典应用，核心思路是“差分标记+前缀和还原”，通过将区间更新转化为点操作，彻底解决了暴力解法的超时问题。代码设计巧妙，下标转换和矩阵大小设计避免了边界判断，原地前缀和优化了空间效率。

该解法不仅适用于“区间加1”，还可推广到“区间加任意常数 k”（仅需将差分更新时的 ++ 和 -- 改为 +=k 和 -=k），是处理矩阵区间更新问题的通用最优思路。掌握二维差分矩阵的核心逻辑，可高效解决各类矩阵区间增减、多查询更新等问题。