2132. 用邮票贴满网格图 (opens new window)

1.二维前缀和+二维差分数组

问题一：如何在O(1)内判断任意位置尺寸为stampHeight x stampWidth的子矩阵是空的？

二维前缀和：定义二维前缀和数组，d[i][j]表示从左上角grid[0][0]到右下角grid[i][j]围成矩阵的所有元素之和。维护该数组时，利用前面的子结果更新计算(子矩阵)。

问题二：如何快速标注子矩阵所有元素都贴上邮票？

前面通过二维前缀和数组，判断以(i,j)位置为起点的子矩阵可以贴上邮票时，每次贴邮票都要遍历O(stampHeight x stampWidth)。因此通过二维差分数组进行优化。

类比一维差分，对某一段连续区域同时加减操作时，只需要在起始位置和终点位置标记。差分数组求前缀和就得到原数组，对于二维前缀和，我们定义sum(i,j)表示从左上角固定(0,0)到(i,j)的矩阵元素之和，因此对于二维差分数组，s[i][j]表示以(i,j)位置为左上角的矩形每个元素同时需要加上的结果。

根据二维差分数组恢复公式：s[i + 1][j + 1] += s[i + 1][j] + s[i][j + 1] - s[i][j]

class Solution {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int m = grid.length;
        int n = grid[0].length;
        //计算二维前缀和:定义d[i][j]表示grid[0][0]到grid[i][j]围成的矩形
        int[][] d = new int[m][n];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i==0&&j==0) d[i][j] = grid[i][j];
                else if(i==0&&j>0) d[i][j] = d[i][j-1]+grid[i][j];
                else if(j==0&&i>0) d[i][j] = d[i - 1][j] + grid[i][j];
                else d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + grid[i][j];
            }
        }
        //根据二维前缀和计算二维差分数组，
        int[][] s = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int a = i + stampHeight - 1;
                int b = j + stampWidth - 1;
                if (a < m && b < n) {
                    int top = i - 1 >= 0 ? d[i - 1][b] : 0;
                    int left = j - 1 >= 0 ? d[a][j - 1] : 0;
                    int topleft = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1][j - 1] : 0;
                    //当前(i,j)位置的矩形可以放置邮票
                    if (d[a][b] - top - left + topleft == 0) {
                        s[i][j]++;
                        if(a+1<m) s[a + 1][j]--;
                        if(b+1<n) s[i][b + 1]--;
                        if(a+1<m&&b+1<n) s[a + 1][b + 1]++;
                    }
                }
            }
        }
        //根据二维差分数组传播二维数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int top = i - 1 >= 0 ? s[i - 1][j] : 0;
                int left = j - 1 >= 0 ? s[i][j - 1] : 0;
                int topleft = i - 1 >= 0 && j - 1 >= 0 ? s[i - 1][j - 1] : 0;
                s[i][j] += top + left - topleft;
                if(grid[i][j]==0&&s[i][j]==0) return false;
            }
        }
        return true;
    }
}