1476. 子矩形查询

1. 题目描述
2. 题解

难度: 中等标签: 数组

1. 题目描述

https://leetcode.cn/problems/subrectangle-queries/
请你实现一个类 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 <= 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
2. 题解
2022-05-06 AC, 简单的数组操作 ```php <?php /**
- Created by PhpStorm
- User: jtahstu
- Time: 2022/5/6 0:45
- Des: 1476. 子矩形查询
- https://leetcode.cn/problems/subrectangle-queries/ */

class SubrectangleQueries {

private $list = [];
/**
 * @param Integer[][] $rectangle
 */
function __construct($rectangle)
{
    $this->list = $rectangle;
}
/**
 * @param Integer $row1
 * @param Integer $col1
 * @param Integer $row2
 * @param Integer $col2
 * @param Integer $newValue
 * @return NULL
 */
function updateSubrectangle($row1, $col1, $row2, $col2, $newValue)
{
    for ($i = $row1; $i <= $row2; $i++) {
        for ($j = $col1; $j <= $col2; $j++) {
            $this->list[$i][$j] = $newValue;
        }
    }
}
/**
 * @param Integer $row
 * @param Integer $col
 * @return Integer
 */
function getValue($row, $col)
{
    return $this->list[$row][$col];
}

}

/**

Your SubrectangleQueries object will be instantiated and called as such:
$obj = SubrectangleQueries($rectangle);
$obj->updateSubrectangle($row1, $col1, $row2, $col2, $newValue);
$ret_2 = $obj->getValue($row, $col); */ $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 echo PHP_EOL . $subrectangleQueries->getValue(0, 2); // 返回 1 $subrectangleQueries->updateSubrectangle(0, 0, 3, 2, 5); // 此次更新后矩形变为： // 5 5 5 // 5 5 5 // 5 5 5 // 5 5 5 echo PHP_EOL . $subrectangleQueries->getValue(0, 2); // 返回 5 echo PHP_EOL . $subrectangleQueries->getValue(3, 1); // 返回 5 $subrectangleQueries->updateSubrectangle(3, 0, 3, 2, 10); // 此次更新后矩形变为： // 5 5 5 // 5 5 5 // 5 5 5 // 10 10 10 echo PHP_EOL . $subrectangleQueries->getValue(3, 1); // 返回 10 echo PHP_EOL . $subrectangleQueries->getValue(0, 2); // 返回 5

/**

暴力直接
执行用时：72 ms, 在所有 PHP 提交中击败了100.00%的用户
内存消耗：24.6 MB, 在所有 PHP 提交中击败了100.00%的用户
通过测试用例：52 / 52 *
咱这也是双百, 热门语言想效率点就是记录操作记录
直接从操作记录里倒序找到当前查找的值是哪次更新的, 找不到就是没操作直接返回原始数组里的值即可
for(int i=len-1; i>=0; i—){ if(C1[i] <= col && col <= C2[i] && R1[i] <= row && row <= R2[i]){
```
 return V[i];
```
} } return rectangle[row][col]; */ ```

1. 题目描述

2. 题解