用邮票贴满网格图
难度:
标签:
题目描述
给你一个 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
代码结果
运行时间: 200 ms, 内存: 33.6 MB
/*
* Solution in Java using Streams
* Idea: Similar approach using streams for readability and functional style.
*/
import java.util.stream.IntStream;
public class SolutionStream {
public boolean canStamp(int[][] grid, int stampHeight, int stampWidth) {
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
IntStream.range(0, m - stampHeight + 1).forEach(i -> {
IntStream.range(0, n - stampWidth + 1).forEach(j -> {
if (canPlaceStamp(grid, i, j, stampHeight, stampWidth)) {
IntStream.range(i, i + stampHeight).forEach(x ->
IntStream.range(j, j + stampWidth).forEach(y -> visited[x][y] = true));
}
});
});
return IntStream.range(0, m).allMatch(i -> IntStream.range(0, n).allMatch(j -> grid[i][j] == 1 || visited[i][j]));
}
private boolean canPlaceStamp(int[][] grid, int row, int col, int stampHeight, int stampWidth) {
return IntStream.range(row, row + stampHeight).allMatch(i ->
IntStream.range(col, col + stampWidth).allMatch(j -> grid[i][j] == 0));
}
}解释
方法:
该题解采用了差分数组和前缀和的方法来高效检查是否可以在二维网格中放置邮票。首先，构造一个前缀和矩阵 psum，用于快速计算任何子矩阵中 1 的数量。如果邮票可以放置在一个子矩阵中，那么这个子矩阵的 psum 值应为 0。接着，使用差分数组 diff 来标记可以开始放置邮票的左上角位置，并通过这个差分数组计算最终每个位置是否可以被邮票覆盖。最后遍历整个网格，如果发现有空白格子（即 grid[i][j] == 0）未被覆盖（即 diff[i][j] == 0），则返回 False，否则返回 True。
时间复杂度:
O(m*n)
空间复杂度:
O(m*n)
代码细节讲解
🦆
如何确保在构建前缀和矩阵时，每个子矩阵中1的数量计算是准确的？
▷🦆
在确定邮票的起始放置点时，如何处理矩阵边缘的情况，确保邮票不超出网格的边界？
▷🦆
差分数组在标记左上角位置时的更新策略是如何确保每个需要覆盖的空格子都能被邮票覆盖？
▷