Medium

题目描述

实现一个 SubrectangleQueries 类，它的构造函数接收一个 rows x cols 的矩形作为整数矩阵，并支持两个方法：

  1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

    • 将左上角坐标为 (row1, col1)、右下角坐标为 (row2, col2) 的子矩形中的所有值更新为 newValue

  2. getValue(int row, int col)

    • 返回矩形中坐标 (row, col) 的当前值

示例 1：

输入
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
输出
[null,1,null,5,5,null,10,5]
解释
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);  
// 初始矩形 (4x3) 如下：
// 1 2 1
// 4 3 4
// 3 2 1
// 1 1 1
subrectangleQueries.getValue(0, 2); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// 更新后的矩形如下：
// 5 5 5
// 5 5 5
// 5 5 5
// 5 5 5 
subrectangleQueries.getValue(0, 2); // 返回 5
subrectangleQueries.getValue(3, 1); // 返回 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// 更新后的矩形如下：
// 5   5   5
// 5   5   5
// 5   5   5
// 10  10  10 
subrectangleQueries.getValue(3, 1); // 返回 10
subrectangleQueries.getValue(0, 2); // 返回 5

提示：

  • 最多执行 500 次操作（包括 updateSubrectangle 和 getValue 两种方法）
  • 1 <= rows, cols <= 100
  • rows == rectangle.length
  • cols == rectangle[i].length
  • 0 <= row1 <= row2 < rows
  • 0 <= col1 <= col2 < cols
  • 1 <= newValue, rectangle[i][j] <= 10^9
  • 0 <= row < rows
  • 0 <= col < cols

解题思路

这道题有两种主要解法，我们分析一下它们的特点：

解法一：直接更新（推荐） 最直观的方法是直接修改原矩阵。每次 updateSubrectangle 时，遍历指定的子矩形区域，将每个位置的值都更新为新值。getValue 直接返回矩阵中对应位置的值。这种方法的优势是查询操作非常快速（O(1)），空间复杂度也最优。

解法二：懒更新优化 另一种思路是记录所有的更新操作，而不立即修改原矩阵。在 getValue 时，倒序遍历所有更新记录，找到最近一次包含查询位置的更新操作，返回对应的新值；如果没有找到，则返回原矩阵的值。这种方法在更新操作很多但查询很少时可能更高效。

考虑到题目约束（最多500次操作，矩阵最大100x100），直接更新法是更优的选择。更新操作的时间复杂度虽然是O(子矩形面积)，但查询是O(1)，且实现简单清晰。在实际应用中，由于矩阵规模不大且操作总数有限，性能完全可以接受。

代码实现

class SubrectangleQueries {
private:
    vector<vector<int>> matrix;
    
public:
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        matrix = rectangle;
    }
    
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                matrix[i][j] = newValue;
            }
        }
    }
    
    int getValue(int row, int col) {
        return matrix[row][col];
    }
};

class SubrectangleQueries:

    def __init__(self, rectangle: List[List[int]]):
        self.matrix = rectangle

    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        for i in range(row1, row2 + 1):
            for j in range(col1, col2 + 1):
                self.matrix[i][j] = newValue

    def getValue(self, row: int, col: int) -> int:
        return self.matrix[row][col]

public class SubrectangleQueries {
    private int[][] matrix;

    public SubrectangleQueries(int[][] rectangle) {
        matrix = rectangle;
    }
    
    public void UpdateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                matrix[i][j] = newValue;
            }
        }
    }
    
    public int GetValue(int row, int col) {
        return matrix[row][col];
    }
}

var SubrectangleQueries = function(rectangle) {
    this.matrix = rectangle;
};

SubrectangleQueries.prototype.updateSubrectangle = function(row1, col1, row2, col2, newValue) {
    for (let i = row1; i <= row2; i++) {
        for (let j = col1; j <= col2; j++) {
            this.matrix[i][j] = newValue;
        }
    }
};

SubrectangleQueries.prototype.getValue = function(row, col) {
    return this.matrix[row][col];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(1)O(rows × cols)
updateSubrectangleO((row2-row1+1) × (col2-col1+1))O(1)
getValueO(1)O(1)

其中 rows 和 cols 是矩阵的行数和列数。更新操作的时间复杂度取决于要更新的子矩形的大小，最坏情况下需要更新整个矩阵。