LeetCode 题解工作台
用邮票贴满网格图
给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。 给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ： 覆盖所有 空 格子。 不覆盖任何 被占据 的格子。 我们可以放入任意…
4
题型
8
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
根据题目描述，每一个空格子都必须被邮票覆盖，而且不能覆盖任何被占据的格子。因此，我们可以遍历二维矩阵，对于每个格子，如果以该格子为左上角的 $stampHeight \times stampWidth$ 的区域内的所有格子都是空格子（即没有被占据），那么我们就可以在该格子处放置一个邮票。 为了快速判断一个区域内的所有格子是否都是空格子，我们可以使用二维前缀和。我们用 表示二维矩阵中从 到 的…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个 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.lengthn == grid[r].length1 <= m, n <= 1051 <= m * n <= 2 * 105grid[r][c]要么是0，要么是1。1 <= stampHeight, stampWidth <= 105
解题思路
方法一：二维前缀和 + 二维差分
根据题目描述，每一个空格子都必须被邮票覆盖，而且不能覆盖任何被占据的格子。因此，我们可以遍历二维矩阵，对于每个格子，如果以该格子为左上角的 的区域内的所有格子都是空格子（即没有被占据），那么我们就可以在该格子处放置一个邮票。
为了快速判断一个区域内的所有格子是否都是空格子，我们可以使用二维前缀和。我们用 表示二维矩阵中从 到 的子矩阵中被占据的格子的数量。即 。
那么以 为左上角，且高度和宽度分别为 和 的子矩阵的右下角坐标为 ，我们可以通过 来计算出该子矩阵中被占据的格子的数量。如果该子矩阵中被占据的格子的数量为 ，那么我们就可以在 处放置一个邮票，放置邮票后，这 的区域内的所有格子都会变成被占据的格子，我们可以用二维差分数组 来记录这一变化。即：
最后，我们对二维差分数组 进行前缀和运算，可以得出每个格子被邮票覆盖的次数。如果某个格子没有被占据，且被邮票覆盖的次数为 ，那么我们就无法将邮票放置在该格子处，因此我们需要返回 。如果所有“没被占据的格子”都成功被邮票覆盖，返回 。
时间复杂度 ，空间复杂度 。其中 和 分别是二维矩阵的高度和宽度。
class Solution:
def possibleToStamp(
self, grid: List[List[int]], stampHeight: int, stampWidth: int
) -> bool:
m, n = len(grid), len(grid[0])
s = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(grid, 1):
for j, v in enumerate(row, 1):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v
d = [[0] * (n + 2) for _ in range(m + 2)]
for i in range(1, m - stampHeight + 2):
for j in range(1, n - stampWidth + 2):
x, y = i + stampHeight - 1, j + stampWidth - 1
if s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] == 0:
d[i][j] += 1
d[i][y + 1] -= 1
d[x + 1][j] -= 1
d[x + 1][y + 1] += 1
for i, row in enumerate(grid, 1):
for j, v in enumerate(row, 1):
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]
if v == 0 and d[i][j] == 0:
return False
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n) for building prefix sums and iterating possible stamp placements. Space complexity is O(m_ n) for the prefix sum matrix and auxiliary coverage arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you can combine greedy choices with fast submatrix checks using prefix sums.
- question_mark
Wants you to avoid O(m _n_ stampHeight*stampWidth) naive checks for stamp placement.
- question_mark
Seeks a method to validate coverage efficiently after greedy placement.
常见陷阱
外企场景- error
Attempting to check each stamp position by iterating over all cells inside the stamp, leading to timeouts.
- error
Overlapping stamps incorrectly without verifying that all empty cells are eventually covered.
- error
Ignoring boundary conditions where stamp placement would exceed grid dimensions.
进阶变体
外企场景- arrow_right_alt
Change the grid to allow rectangular stamps of varying dimensions and compute coverage feasibility.
- arrow_right_alt
Introduce obstacles that cannot be stamped and check if complete coverage of remaining empty cells is possible.
- arrow_right_alt
Count the minimum number of stamps required to cover all empty cells using a similar greedy plus validation approach.