LeetCode 2132. 用邮票贴满网格图：二维前缀和 + 二维差分

【LetMeFly】2132.用邮票贴满网格图：二维前缀和 + 二维差分

力扣题目链接：https://leetcode.cn/problems/stamping-the-grid/

给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。

给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下限制和要求：

覆盖所有空格子。
不覆盖任何 被占据 的格子。
我们可以放入任意数目的邮票。
邮票可以相互有重叠部分。
邮票不允许旋转。
邮票必须完全在矩阵内。

如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。

示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。

示例 2：

输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
输出：false 
解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

提示：

m == grid.length
n == grid[r].length
1 <= m, n <= 10⁵
1 <= m * n <= 2 * 10⁵
grid[r][c] 要么是 0 ，要么是 1 。
1 <= stampHeight, stampWidth <= 10⁵

方法一：二维前缀和 + 二维差分

二维前缀和预处理好后，可以在 $O (1)$ 的时间内查出任意矩形的所有元素之和。（ $p re f i x [i + 1] [j + 1]$ 是 $ma t [i] [j]$ 及其左上角所有元素组成的矩阵的和）

若矩形内每个元素都加d，则可以在 $O (1)$ 的时间内记录到差分数组中。最后能以 $O (mn)$ 的时间还原出原数组。（按求前缀和的方式对差分数组计算，即可得到原矩阵）

因为贴邮票的次数不限，因此我们决定：能贴的下就贴。最后，看看是否还有空格即可。

具体思路：

消耗 $O (mn)$ 的时间计算出前缀和数组。

遍历矩阵中的每个空白位置，若以这个位置为左上角可以贴邮票（通过前缀和能很快确认），则贴邮票（通过差分数组能很快记录）。

最终再消耗 $O (mn)$ 的时间还原出贴发票后的矩阵。

时间复杂度 $O (s i ze (g r i d))$
空间复杂度 $O (s i ze (g r i d))$

AC代码

C++

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> prefix(n + 1, vector<int>(m + 1)), diff(n + 2, vector<int>(m + 2));
        // prefix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
            }
        }
        // stamp
        for (int i = 0; i + h - 1 < n; i++) {
            for (int j = 0; j + w - 1 < m; j++) {
                // (i, j) -> (i + h - 1, j + w - 1)
                if (!grid[i][j] && !(prefix[i + h][j + w] - prefix[i + h][j] - prefix[i][j + w] + prefix[i][j])) {
                    diff[i + 1][j + 1]++;
                    diff[i + 1][j + w + 1]--;
                    diff[i + h + 1][j + 1]--;
                    diff[i + h + 1][j + w + 1]++;
                }
            }
        }
        // un-diff
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                diff[i + 1][j + 1] += diff[i][j + 1] + diff[i + 1][j] - diff[i][j];
                if (!grid[i][j] && !diff[i + 1][j + 1]) {
                    return false;
                }
            }
        }
        return true;
    }
};

Python

# from typing import List

class Solution:
    def possibleToStamp(self, grid: List[List[int]], h: int, w: int) -> bool:
        n, m = len(grid), len(grid[0])
        prefix = [[0] * (m + 1) for _ in range(n + 1)]
        diff = [[0] * (m + 2) for _ in range(n + 2)]
        # get-prefix
        for i in range(n):
            for j in range(m):
                prefix[i + 1][j + 1] = grid[i][j] + prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j]
        # stamp
        for i in range(n - h + 1):
            for j in range(m - w + 1):
                # (i, j) -> (i + h - 1, j + w - 1)
                if not grid[i][j] and not (prefix[i + h][j + w] + prefix[i][j] - prefix[i + h][j] - prefix[i][j + w]):
                    diff[i + 1][j + 1] += 1
                    diff[i + h + 1][j + 1] -= 1
                    diff[i + 1][j + w + 1] -= 1
                    diff[i + h + 1][j + w + 1] += 1
        # un-diff
        for i in range(n):
            for j in range(m):
                diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j]
                if not grid[i][j] and not diff[i + 1][j + 1]:
                    return False
        return True