LeetCode 1476. 子矩形查詢

• 題目描述
• 解題思路
• 代碼
• 複雜度分析

題目描述

題目連結

請你實作一個類 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 
subrectangleQueries.getValue(0, 2); // 傳回 5
subrectangleQueries.getValue(3, 1); // 傳回 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// 此次更新後矩形變為：
// 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           

複制

解題思路

隻需要在 SubrectangleQueries 這個類裡建立一個内部的數組，并深度拷貝 rectangle 的值即可。

代碼

class SubrectangleQueries {

    int[][] matrix;

    public SubrectangleQueries(int[][] rectangle) {
        matrix = new int[rectangle.length][rectangle[0].length];
        for (int i = 0; i < rectangle.length; i++) {
            for (int j = 0; j < rectangle[0].length; j++) {
                matrix[i][j] = rectangle[i][j];
            }
        }
    }

    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        if (row1 > row2 || col1 > col2) {
            return;
        }
        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];
    }
}           

複制

複雜度分析

時間複雜度：getValue $O(1)$

空間複雜度：$O(row * col)$