LeetCode 803. 打砖块

约 10 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 快手
标签
数组 矩阵 并查集

题目描述

✅ 803. 打砖块

image-20260929104839237

image-20260929104839383

image-20260929104839470

题意分析

砖块只有直接位于顶行，或能沿四方向相邻砖块连到顶行，才保持稳定。依次敲击给定位置，统计每次因此失去支撑而掉落的其他砖块数，不包含直接敲掉的一块；敲到空位时答案为 0。题目保证敲击位置互不相同。

解法：逆向并查集 + 虚拟顶部

核心思路

[!blue]

正向删去一块砖可能让连通块分裂，普通并查集不能直接维护这种拆分。把过程倒过来，从移除所有敲击位置的副本开始逐块恢复，就只会增加节点和连接，可以用并查集合并。

额外建立编号为 m * n 的虚拟顶部节点，把所有顶行砖块与它相连。它所在集合中的真实砖块恰好是稳定砖块。集合根可能因合并改变，所以查询规模时要先 find(top)，不能直接读取固定下标的规模。

先复制原网格，只把所有敲击位置置为 0，再合并剩余相邻砖块。这个副本保留了悬空部分，并不等同于正向执行后的实际棋盘；只有与虚拟顶部连通的部分代表稳定状态。不能提前删掉悬空砖块，否则恢复支撑时就无法把它们一起接回顶部。

倒序处理第 k 次敲击时，副本相当于原网格只移除了第 0..k 个敲击位置。恢复当前位置并合并四邻后，就撤销了这次删除。设顶部集合规模从 prev 变为 cur，增加的稳定砖块就是正向这一步失去顶部连接的砖块，其中包含直接恢复的这一块，所以额外掉落数为 cur - prev - 1。

如果恢复后仍不连通顶部，规模增量为 0，应返回 0，所以统一取 max(0, cur - prev - 1)。原网格本就没有砖的敲击直接跳过；若原来有砖、却在更早的正向敲击中已经掉落，此时恢复它仍无法连回顶部，也自然贡献 0。虚拟顶部节点始终存在于集合中，在前后差值中会抵消。

初次建图只需检查上方、左方，每条无向相邻边都会被处理一次；倒序恢复时邻居可能出现在任意方向，必须检查全部四邻。合并相同根时不重复累加规模，避免多条连接重复计数。

解题步骤

  1. 复制网格，并将所有命中的位置从副本移除。
  2. 合并副本中的相邻砖块，将顶行连接到虚拟顶部。
  3. 倒序处理命中位置：原网格该位置没有砖块则答案为零。
  4. 恢复砖块并合并四邻，记录顶部大小增量减一后的非负值。

代码实现

class Solution {
    private int[] parent;
    private int[] size;

    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length;
        int n = grid[0].length;
        // 额外节点代表屋顶，所有顶行砖块与它相连。
        int top = m * n;

        int[][] copy = new int[m][n];

        for (int i = 0; i < m; i++) {
            copy[i] = grid[i].clone();
        }

        for (int[] h : hits) {
            copy[h[0]][h[1]] = 0;
        }

        parent = new int[top + 1];
        size = new int[top + 1];

        for (int i = 0; i <= top; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (copy[i][j] != 1) {
                    continue;
                }

                int id = idx(i, j, n);

                if (i == 0) {
                    union(id, top);
                }

                // 初建图只看上方和左方即可覆盖全部相邻边；恢复时再检查四邻。
                if (i > 0 && copy[i - 1][j] == 1) {
                    union(id, idx(i - 1, j, n));
                }

                if (j > 0 && copy[i][j - 1] == 1) {
                    union(id, idx(i, j - 1, n));
                }
            }
        }

        int[] answer = new int[hits.length];
        int[][] dirs = {
            {0, 1},
            {0, -1},
            {1, 0},
            {-1, 0},
        };

        for (int k = hits.length - 1; k >= 0; k--) {
            int r = hits[k][0];
            int c = hits[k][1];

            if (grid[r][c] == 0) {
                continue;
            }

            // 恢复前记录顶部集合大小，只统计本次新增的稳定部分。
            int prev = getSize(top);

            copy[r][c] = 1;
            int id = idx(r, c, n);

            if (r == 0) {
                union(id, top);
            }

            for (int[] d : dirs) {
                int nr = r + d[0];
                int nc = c + d[1];

                if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                    continue;
                }

                if (copy[nr][nc] == 1) {
                    union(id, idx(nr, nc, n));
                }
            }

            int cur = getSize(top);

            // 顶部增量扣除刚恢复的砖块，悬空恢复的答案取零。
            answer[k] = Math.max(0, cur - prev - 1);
        }

        return answer;
    }

    private int idx(int r, int c, int n) {
        return r * n + c;
    }

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    private void union(int x, int y) {
        int px = find(x);
        int py = find(y);

        if (px == py) {
            return;
        }

        if (size[px] < size[py]) {
            int tmp = px;

            px = py;
            py = tmp;
        }

        parent[py] = px;
        size[px] += size[py];
    }

    private int getSize(int x) {
        return size[find(x)];
    }
}

type UnionFind struct {
    parent []int
    size   []int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := range parent {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent, size}
}

func (uf *UnionFind) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) union(x, y int) {
    px, py := uf.find(x), uf.find(y)
    if px == py {
        return
    }
    if uf.size[px] < uf.size[py] {
        px, py = py, px
    }
    uf.parent[py] = px
    uf.size[px] += uf.size[py]
}

func (uf *UnionFind) getSize(x int) int {
    return uf.size[uf.find(x)]
}

func hitBricks(grid [][]int, hits [][]int) []int {
    m, n := len(grid), len(grid[0])
    // 额外节点代表屋顶，所有顶行砖块与它相连。
    top := m * n

    idx := func(r, c int) int { return r*n + c }

    copy2 := make([][]int, m)
    for i := range copy2 {
        copy2[i] = make([]int, n)
        copy(copy2[i], grid[i])
    }
    for _, hit := range hits {
        copy2[hit[0]][hit[1]] = 0
    }

    uf := newUnionFind(m*n + 1)

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if copy2[i][j] == 1 {
                if i == 0 {
                    uf.union(top, idx(i, j))
                }
                // 初建图只看上方和左方即可覆盖全部相邻边；恢复时再检查四邻。
                if i > 0 && copy2[i-1][j] == 1 {
                    uf.union(idx(i, j), idx(i-1, j))
                }
                if j > 0 && copy2[i][j-1] == 1 {
                    uf.union(idx(i, j), idx(i, j-1))
                }
            }
        }
    }

    dirs := [][2]int{
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0},
    }
    result := make([]int, len(hits))

    for k := len(hits) - 1; k >= 0; k-- {
        r, c := hits[k][0], hits[k][1]

        if grid[r][c] == 0 {
            continue
        }

        // 恢复前记录顶部集合大小，只统计本次新增的稳定部分。
        prevTop := uf.getSize(top)
        copy2[r][c] = 1

        if r == 0 {
            uf.union(idx(r, c), top)
        }

        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < m && nc >= 0 && nc < n && copy2[nr][nc] == 1 {
                uf.union(idx(r, c), idx(nr, nc))
            }
        }

        currTop := uf.getSize(top)
        // 顶部增量扣除刚恢复的砖块，悬空恢复的答案取零。
        if currTop-prevTop-1 > 0 {
            result[k] = currTop - prevTop - 1
        }
    }

    return result
}

复杂度分析

  • 时间复杂度：网格有 mn 个位置、q 次操作时，时间为 $O((mn+q)\alpha(mn+1))$。
  • 空间复杂度：$O(mn)$，网格副本及并查集，另有 $O(q)$ 输出。

关键点总结

[!green]

  • 顶部集合大小的变化决定新增稳定砖块数。
  • 被恢复的砖块不计入掉落答案，因此需要减一并与零取最大值。
  • 原网格有砖不代表正向轮到该次敲击时它仍未掉落。

易错点总结

[!yellow]

  • 正向使用普通并查集直接删除节点：无法正确拆分原有连通分量。
  • 使用当前砖块所在集合大小代替顶部增量：悬空集合并不稳定。
  • 忘记排除直接敲掉的砖块：答案多算一。
  • 将副本中的悬空砖块提前全部清除：破坏倒序恢复所需的连接关系。

相似题目

题目 难度 关联与区别
305. 岛屿数量 II 困难 动态加点比动态删点更适合并查集，本题可倒序恢复砖块，把删除转为合并。
827. 最大人工岛 困难 同样先维护连通块大小，本题关注与屋顶连通的变化，原题关注一次加点后的最大岛屿。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/23455823
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！