筆記：【演算法新手村】[初階]筆記06 - 差分(二維)

題目翻譯

給定一個正整數 n，代表一個初始全為 0、大小為 n × n 的二維矩陣 mat（索引從 0 開始）。
另外給定一個二維整數陣列 query。針對每個 query[i] = [row1ᵢ, col1ᵢ, row2ᵢ, col2ᵢ]，你需要執行以下操作：
將矩陣中以左上角 (row1ᵢ, col1ᵢ) 到右下角 (row2ᵢ, col2ᵢ) 所定義的子矩陣內每一個元素都加 1。也就是說，對於所有滿足 row1ᵢ ≤ x ≤ row2ᵢ 且 col1ᵢ ≤ y ≤ col2ᵢ 的位置，將 mat[x][y] 的值加 1。

請回傳執行完所有查詢後的最終矩陣 mat。

解題思路

這題很明顯，矩陣子區間進行加法要想到二維差分，唯一要注意的是索引不要越界!

程式碼實作 (C++)

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> d(n, vector<int>(n, 0));

        for(auto x : queries)
        {
            int x1 = x[0];
            int y1 = x[1];
            int x2 = x[2];
            int y2 = x[3];

            d[x1][y1] += 1;
            if (y2 + 1 < n) {
                d[x1][y2 + 1] -= 1;
            }
            
            if (x2 + 1 < n) {
                d[x2 + 1][y1] -= 1;
            }
            
            if (x2 + 1 < n && y2 + 1 < n) {
                d[x2 + 1][y2 + 1] += 1;
            }
        }

        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(i > 0){
                    d[i][j] += d[i-1][j];
                }                

                if(j > 0){
                    d[i][j] += d[i][j - 1];
                }

                if(i > 0 && j > 0){
                     d[i][j] -= d[i-1][j-1];
                }    
            }
        }
        return d;
    }
};