二维差分：用邮票贴满网格图

字数统计: 2.7k字 | 阅读时长: 12分

2023-12-14

摘要: 二维差分

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在一维数组上，前缀和与差分是一种常见的处理区间求和问题的算法，参考文章【模板】前缀和与差分。

如果二维的矩阵上有类似的与求和有关的问题，一种常见的思路是二维转一维，枚举行 $i$，在固定 $i$ 的时候看 $j = 0,1,\cdots,m-1$，此时就是一个一维上的问题了，一共解决 $i=0,1,\cdots,n-1$ 共 $n$ 次一维上的问题得到答案。可以这么解决的问题很多，参考文章二维转一维。

而有时上述的二维转一维的做法解决不了问题，而需要直接维护矩形上的操作。本文的题目就是一个例子。

本文我们以一个例题看一下二维差分的算法原理与代码模板。

题目

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

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

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

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

提示：

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

示例 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
解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

题解

分析

记矩阵的高度和宽度为 $n, m$，邮票的高度和宽度为 $N, M$。

由于邮票不能旋转，因此需要贴邮票的地方，如果宽度方向有矩阵边界或禁入点，则边界或禁入点之间夹着的宽度必须大于等于 $M$；同样地，高度方向的边界和禁入点之间夹着的高度必须大于等于 $N$。

因此一个比较直接的思路是找到矩阵上所有位置边界与禁入点之间夹着的最小高度 $minN$、最小宽度 $minM$。如果 $minN > N$ 或 $minM > M$，那么肯定无法贴满邮票。问题在于如果满足 $minM < M$ 且 $minN < N$，是否就一定可以贴满。

这里不仔细分析的话容易上当，事实上这是不成立的，反例如下：

grid =
[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]

stampHeight =
4

stampWidth =
5

邮票高度和宽度分别为 $3, 4$，矩阵中有四个禁入点，禁入点与边界之间的距离充足，而禁入点内部的阴影点无法用邮票覆盖到，然后再一看，每个非禁入点都满足被禁入点与边界夹着的高度大于 3、宽度小于 4 的条件。

因此我们需要更加细致地对每个非禁入点进行判断，如果枚举每个非禁入点，再枚举所有可以覆盖到该点的子矩形，在进行判断，时间复杂度会很高，具体为枚举每个非禁入点 $O(MN)$，枚举所有覆盖该点的子矩形 $O(mn)$，判断过程通过前缀和可以 $O(1)$ 解决，但总时间复杂度依然为 $O(MNmn)$。

从上到下枚举 $i = 0,1,\cdots,n-N$，然后从左到右枚举 $j = 0,1,\cdots,m-M$，我们记录一个 $visited$，$visited(i, j) > 0$ 表示已经确认 $(i, j)$ 位置邮票可以覆盖到。

枚举到 $(i, j)$ 时，考察以 $(i, j)$ 为左上角的高度宽度分别为 $N, M$ 的子矩形。如果该子矩形可以放入，则把左上角位置在 $(i, j)$ 的子矩形在 $visited$ 上都加 $1$。

但是这样的话 $visited$ 上会有大量的加 $1$ 操作，我们需要一种高效的维护子矩形同时加 $1$ 操作，并且在加 1 操作结束后，查询各个位置的若干次加 $1$ 结果的数据结构。

算法：二维差分

回顾一维差分，参考文章差分维护区间加法。

假设有前缀和序列 $S(0), S(1), \cdots, S(n)$，那么差分序列 $a(0), a(1), \cdots, a(n)$ 就等于原序列。也就是从前缀和序列到原序列的关系如下：

$a(i) = S(i+1) - S(i)$

考虑相反的方向，如果原序列 $a(0), a(1), \cdots, a(n)$，已经有了差分序列 $b(0), b(1), \cdots, b(n)$，其中 $b(0) = a(0) - 0$，$b(i) = a(i) - a(i-1)$，这样的话对差分序列求前缀和，即得原序列。也就是从差分序列计算原序列的计算公式如下，也就是前缀和：

$a(i) = \sum\limits_{j=0}\limits^{i}b(j)$

如果要在元素列 $\vec{a}$ 上的区间 $[l, r]$ 上都加 $x$，需要加 $r - l + 1$ 次，在差分序列上只需要加 2 次：$b(l) + x$、$b(r+1) - x$。区间加法结束后，将 $\vec{b}$ 求前缀和，所得即为加法操作后的原序列 $\vec{a}$。

类似地，对于矩阵 $A$，我们如果有二维前缀和矩阵 $S(i,j)$，从前缀和矩阵到原矩阵的关系如下：

$A(i, j) = S(i + 1, j + 1) - S(i, j + 1) - S(i + 1, j) + S(i, j)$

其中 $S$ 的高和宽均比 $A$ 大 $1$，$S(i + 1, j + 1) = \sum\limits_{x=0}\limits^{i}\sum\limits_{y=0}\limits^{j}A(x, y)$。

同样考虑相反方向，如果把 $S$ 视为原矩阵，把 $A$ 视为差分矩阵，我们需要通过以上关系找到从差分矩阵到原矩阵的计算公式。

对原矩阵 $A(0:n-1, 0:m-1)$。如果我们已经有了差分矩阵 $B$：

$\begin{align} B(i, j) &= A(i, j) - A(i - 1, j) - A(i, j - 1) + A(i - 1, j - 1) \quad i, j > 0 \\ B(0, 0) &= A(0, 0) \quad i, j = 0 \\ B(i, 0) &= A(i, 0) - A(i - 1, 0) \quad j = 0, i > 0 \\ B(0, j) &= A(0, j) - A(0, j - 1) \quad i = 0, j < 0 \\ \end{align}$

这样从差分矩阵到原矩阵的计算公式如下，也就是二维前缀和：

$A(i, j) = \sum\limits_{x=0}\limits^{i}\sum\limits_{y=0}\limits^{j}B(x, y) \\ i=0,1,\cdots,n-1 \\ j=0,1,\cdots,m-1 \\$

如果要对左上角 $(x_1, y_1)$，右下角 $(x_2, y_2)$ 的矩形范围加 $v$，在差分矩阵上的操作如下：

首先 $B(x_1, y_1)$ 需要加 $v$，这样 $v$ 在 $(x_1, y_1)$ 的右边和下边方向都会贡献。
但 $B(x_1, y_1)$ 加 $v$ 往下只能贡献到 $x_{2}$，因此 $B(x_2 + 1, y_1)$ 减 $v$。
但 $B(x_1, y_1)$ 加 $v$ 往右只能贡献到 $y_{2}$，因此 $B(x_1, y_2 + 1)$ 减 $v$。
$B(x_2 + 1, y_1)$ 和 $B(x_1, y_2 + 1)$ 的减 $v$ 在 $B(x_2 + 1, y_2 + 1)$ 及其右下的区域会贡献两份，因此 $B(x_2 + 1, y_2 + 1)$ 需要加 $v$。

代码 (C++，模板)

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int n = grid.size();
        int m = grid[0].size();

        vector<vector<int>> sums(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                sums[i][j] = grid[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];

        vector<vector<int>> diff(n + 1, vector<int>(m + 1));
        for(int i = 0; i <= n - stampHeight; ++i)
            for(int j = 0; j <= m - stampWidth; ++j)
            {
                int x1 = i;
                int y1 = j;
                int x2 = i + stampHeight - 1;
                int y2 = j + stampWidth - 1;
                if(sums[x2 + 1][y2 + 1] - sums[x2 + 1][y1] - sums[x1][y2 + 1] + sums[x1][y1] == 0)
                {
                    diff[x1][y1] += 1;
                    diff[x2 + 1][y1] -= 1;
                    diff[x1][y2 + 1] -= 1;
                    diff[x2 + 1][y2 + 1] += 1;
                }
            }

        vector<vector<int>> visited(n + 1, vector<int>(m + 1));
        visited[0][0] = diff[0][0];
        for(int i = 1; i <= n; ++i)
            visited[i][0] = diff[i][0] + visited[i - 1][0];
        for(int j = 1; j <= m; ++j)
            visited[0][j] = diff[0][j] + visited[0][j - 1];
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                visited[i][j] = diff[i][j] + visited[i][j - 1] + visited[i - 1][j] - visited[i - 1][j - 1];
            }

        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(grid[i][j] == 0 && visited[i][j] == 0)
                    return false;
            }
        return true;
    }
};

代码 (Python，模板)

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        n = len(grid)
        m = len(grid[0])

        sums = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                sums[i][j] = grid[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1]

        diff = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
        for i in range(n - stampHeight + 1):
            for j in range(m - stampWidth + 1):
                x1 = i
                y1 = j
                x2 = i + stampHeight - 1
                y2 = j + stampWidth - 1
                if sums[x2 + 1][y2 + 1] - sums[x2 + 1][y1] - sums[x1][y2 + 1] + sums[x1][y1] == 0:
                    diff[x1][y1] += 1
                    diff[x2 + 1][y1] -= 1
                    diff[x1][y2 + 1] -= 1
                    diff[x2 + 1][y2 + 1] += 1

        visited = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
        visited[0][0] = diff[0][0]
        for i in range(1, n + 1):
            visited[i][0] = diff[i][0] + visited[i - 1][0]
        for j in range(1, m + 1):
            visited[0][j] = diff[0][j] + visited[0][j - 1]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                visited[i][j] = diff[i][j] + visited[i][j - 1] + visited[i - 1][j] - visited[i - 1][j - 1]

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0 and visited[i][j] == 0:
                    return False
        return True

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法基础算法

二维差分：用邮票贴满网格图

题目

题解

分析

算法：二维差分

代码 (C++，模板)

代码 (Python，模板)