Hard
题目描述
给你一个 m x n 的二进制网格，其中 1 表示砖块，0 表示空位。砖块是稳定的如果：
- 它直接连接到网格的顶部，或
- 它的四个相邻单元格中至少有一个其他砖块是稳定的。
你还会得到一个数组 hits，这是我们要应用的一系列擦除操作。每次我们想要擦除位置 hits[i] = (rowi, coli) 的砖块。该位置的砖块（如果存在）将消失。由于该擦除操作，一些其他砖块可能不再稳定并会掉落。一旦砖块掉落，它会立即从网格中擦除（即，它不会落在其他稳定的砖块上）。
返回一个数组 result，其中每个 result[i] 是应用第 i 次擦除操作后将掉落的砖块数量。
注意，擦除操作可能涉及没有砖块的位置，如果是这样，则不会有砖块掉落。
示例 1：
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：从网格开始：
[[1,0,0,0],
[1,1,1,0]]
我们擦除 (1,0) 处的砖块，得到网格：
[[1,0,0,0],
[0,1,1,0]]
两个下划线砖块不再稳定，因为它们既不连接到顶部，也不与另一个稳定砖块相邻，所以它们会掉落。结果网格是：
[[1,0,0,0],
[0,0,0,0]]
因此结果是 [2]。
示例 2：
输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：从网格开始：
[[1,0,0,0],
[1,1,0,0]]
我们擦除 (1,1) 处的砖块，得到网格：
[[1,0,0,0],
[1,0,0,0]]
所有剩余砖块仍然稳定，所以没有砖块掉落。网格保持不变：
[[1,0,0,0],
[1,0,0,0]]
接下来，我们擦除 (1,0) 处的砖块，得到网格：
[[1,0,0,0],
[0,0,0,0]]
再一次，所有剩余砖块仍然稳定，所以没有砖块掉落。
因此结果是 [0,0]。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j]是0或11 <= hits.length <= 4 * 10^4hits[i].length == 20 <= xi <= m - 10 <= yi <= n - 1- 所有
(xi, yi)都是唯一的
解题思路
这道题的核心思想是逆向思维。由于需要计算每次打击后掉落的砖块数量，正向模拟会很复杂，因为需要维护连通性状态。
解题思路
逆向处理：先将所有要打击的砖块移除，然后逆序执行添加操作，计算每次添加砖块后连通的新砖块数量。
并查集维护连通性：使用并查集来维护砖块的连通性。设置一个虚拟根节点代表"与顶部连通"的状态。
算法流程：
- 预处理：将所有hit位置的砖块标记为2（表示将被移除）
- 初始化：将剩余的砖块用并查集连接，第一行砖块连接到虚拟根节点
- 逆序处理每个hit：
- 恢复该位置的砖块
- 计算恢复前与虚拟根连通的砖块数量
- 将该砖块与相邻稳定砖块连接
- 计算恢复后与虚拟根连通的砖块数量
- 两者差值即为该次hit导致掉落的砖块数
时间复杂度优化：并查集使用路径压缩和按秩合并，单次操作近似O(1)。
这种方法的巧妙之处在于将"砖块掉落"转化为"砖块连接"，大大简化了问题的复杂度。
代码实现
class Solution {
public:
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> g(grid);
// Mark all hit positions
for (auto& hit : hits) {
g[hit[0]][hit[1]] = 0;
}
// Union-Find
vector<int> parent(m * n + 1);
vector<int> size(m * n + 1, 1);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
};
auto unite = [&](int x, int y) {
x = find(x), y = find(y);
if (x != y) {
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
}
};
int roof = m * n; // Virtual roof node
// Connect initial stable bricks
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 1) {
if (i == 0) unite(i * n + j, roof);
if (i > 0 && g[i-1][j] == 1) unite(i * n + j, (i-1) * n + j);
if (j > 0 && g[i][j-1] == 1) unite(i * n + j, i * n + j - 1);
}
}
}
vector<int> result(hits.size());
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// Process hits in reverse order
for (int k = hits.size() - 1; k >= 0; k--) {
int x = hits[k][0], y = hits[k][1];
if (grid[x][y] == 0) continue;
int prevSize = size[find(roof)];
g[x][y] = 1;
if (x == 0) unite(x * n + y, roof);
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && g[nx][ny] == 1) {
unite(x * n + y, nx * n + ny);
}
}
int newSize = size[find(roof)];
result[k] = max(0, newSize - prevSize - 1);
}
return result;
}
};
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
m, n = len(grid), len(grid[0])
g = [row[:] for row in grid]
# Mark all hit positions
for x, y in hits:
g[x][y] = 0
# Union-Find
parent = list(range(m * n + 1))
size = [1] * (m * n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x, y):
px, py = find(x), find(y)
if px != py:
if size[px] < size[py]:
px, py = py, px
parent[py] = px
size[px] += size[py]
roof = m * n # Virtual roof node
# Connect initial stable bricks
for i in range(m):
for j in range(n):
if g[i][j] == 1:
if i == 0:
unite(i * n + j, roof)
if i > 0 and g[i-1][j] == 1:
unite(i * n + j, (i-1) * n + j)
if j > 0 and g[i][j-1] == 1:
unite(i * n + j, i * n + j - 1)
result = [0] * len(hits)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Process hits in reverse order
for k in range(len(hits) - 1, -1, -1):
x, y = hits[k]
if grid[x][y] == 0:
continue
prev_size = size[find(roof)]
g[x][y] = 1
if x == 0:
unite(x * n + y, roof)
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and g[nx][ny] == 1:
unite(x * n + y, nx * n + ny)
new_size = size[find(roof)]
result[k] = max(0, new_size - prev_size - 1)
return result
public class Solution {
public int[] HitBricks(int[][] grid, int[][] hits) {
int m = grid.Length, n = grid[0].Length;
int[,] g = new int[m, n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
g[i, j] = grid[i][j];
}
}
// Mark all hit positions
foreach (var hit in hits) {
g[hit[0], hit[1]] = 0;
}
// Union-Find
int[] parent = new int[m * n + 1];
int[] size = new int[m * n + 1];
for (int i = 0; i <= m * n; i++) {
parent[i] = i;
size[i] = 1;
}
int Find(int x) {
return parent[x] == x ? x : parent[x] = Find(parent[x]);
}
void Unite(int x, int y) {
x = Find(x);
y = Find(y);
if (x != y) {
if (size[x] < size[y]) {
int temp = x; x = y; y = temp;
}
parent[y] = x;
size[x] += size[y];
}
}
int roof = m * n; // Virtual roof node
// Connect initial stable bricks
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (g[i, j] == 1) {
if (i == 0) Unite(i * n + j, roof);
if (i > 0 && g[i-1, j] == 1) Unite(i * n + j, (i-1) * n + j);
if (j > 0 && g[i, j-1] == 1) Unite(i * n + j, i * n + j - 1);
}
}
}
int[] result = new int[hits.Length];
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// Process hits in reverse order
for (int k = hits.Length - 1; k >= 0; k--) {
int x = hits[k][0], y = hits[k][1];
if (grid[x][y] == 0) continue;
int prevSize = size[Find(roof)];
g[x, y] = 1;
if (x == 0) Unite(x * n + y, roof);
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && g[nx, ny] == 1) {
Unite(x * n + y, nx * n + ny);
}
}
int newSize = size[Find(roof)];
result[k] = Math.Max(0, newSize - prevSize - 1);
}
return result;
}
}
var hitBricks = function(grid, hits) {
const m = grid.length, n = grid[0].length;
const g = grid.map(row => [...row]);
// Mark all hit positions
for (const [x, y] of hits) {
g[x][y] = 0;
}
// Union-Find
const parent = Array.from({length: m * n + 1}, (_, i) => i);
const size = Array(m * n + 1).fill(1);
const find = (x) => {
return parent[x]
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |