英文原文
Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:
1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
- Updates all values with
newValuein the subrectangle whose upper left coordinate is(row1,col1)and bottom right coordinate is(row2,col2).
2. getValue(int row, int col)
- Returns the current value of the coordinate
(row,col)from the rectangle.
Example 1:
Input ["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]] Output [null,1,null,5,5,null,10,5] Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]); // The initial rectangle (4x3) looks like: // 1 2 1 // 4 3 4 // 3 2 1 // 1 1 1 subrectangleQueries.getValue(0, 2); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 5 5 5 subrectangleQueries.getValue(0, 2); // return 5 subrectangleQueries.getValue(3, 1); // return 5 subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 10 10 10 subrectangleQueries.getValue(3, 1); // return 10 subrectangleQueries.getValue(0, 2); // return 5
Example 2:
Input ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"] [[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]] Output [null,1,null,100,100,null,20] Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]); subrectangleQueries.getValue(0, 0); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); // return 100 subrectangleQueries.getValue(2, 2); // return 100 subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20); subrectangleQueries.getValue(2, 2); // return 20
Constraints:
- There will be at most
500operations considering both methods:updateSubrectangleandgetValue. 1 <= rows, cols <= 100rows == rectangle.lengthcols == rectangle[i].length0 <= row1 <= row2 < rows0 <= col1 <= col2 < cols1 <= newValue, rectangle[i][j] <= 10^90 <= row < rows0 <= col < cols
中文题目
请你实现一个类 SubrectangleQueries ，它的构造函数的参数是一个 rows x cols 的矩形（这里用整数矩阵表示），并支持以下两种操作：
1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
- 用
newValue更新以(row1,col1)为左上角且以(row2,col2)为右下角的子矩形。
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
示例 2：
输入： ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"] [[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]] 输出： [null,1,null,100,100,null,20] 解释： SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]); subrectangleQueries.getValue(0, 0); // 返回 1 subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); // 返回 100 subrectangleQueries.getValue(2, 2); // 返回 100 subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20); subrectangleQueries.getValue(2, 2); // 返回 20
提示：
- 最多有
500次updateSubrectangle和getValue操作。 1 <= rows, cols <= 100rows == rectangle.lengthcols == rectangle[i].length0 <= row1 <= row2 < rows0 <= col1 <= col2 < cols1 <= newValue, rectangle[i][j] <= 10^90 <= row < rows0 <= col < cols
通过代码
高赞题解
这道题暴力模拟就可以通过，不多说了。但是，这个问题可以不暴力更新矩阵的内容。
我们可以设置一个history的数组，记录每次调用updateSubrectangle的信息。这样，updateSubrectangle的复杂度是 O(1) 的。
相应的，在 getValue 的过程中，我们只需要倒序查找我们记录的 history，如果发现我们要查找的 (row, col) 包含在某一次历史更新的位置中，直接返回这个历史更新值就好了。否则的，历史更新没有动过这个位置，返回原始矩阵中这个位置的值。
我的参考代码如下（C++）：
class SubrectangleQueries {
private:
vector<vector<int>> rectangle;
vector<vector<int>> history;
public:
SubrectangleQueries(vector<vector<int>>& rectangle) : rectangle(rectangle) {}
void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
history.push_back({row1, col1, row2, col2, newValue});
}
int getValue(int row, int col) {
for(int i = history.size() - 1; i >= 0; i --)
if(history[i][0] <= row && row <= history[i][2] &&
history[i][1] <= col && col <= history[i][3])
return history[i][4];
return rectangle[row][col];
}
};对于这个思路，update 是 O(1) 的，而 get 是 O(k) 的，k 是历史有过多少次更新。根据题意， k 最多为 500。
这是比暴力更新矩阵中的元素要快的。因为暴力更新矩阵中的元素，时间复杂度是 O(r * c) 的。根据题意，在这个问题中，1 <= r, c <= 100，r * c 最大可以达到 10000。
实际上，这个思路和矩阵的大小没有关系，只和调用更新操作的次数有关。所以，即使矩阵更大，也可以应付。
当然，对于小矩阵，超多调用的情况，这个思路就有劣势了。所以可以根据题目中的数据限制条件做选择：）
觉得有帮助请点赞哇！
大家加油！：）
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 12917 | 14918 | 86.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
