LeetCode 803. 打砖块

2023-04-23 HGNULB 约 19 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 803. 打砖块

题意分析

给定一个 $m \times n$ 的二值网格，1 表示砖块、0 表示空。一块砖是稳定的，当且仅当它位于第一行，或者它与某块稳定的砖四向相邻。现在按顺序执行一串敲击 hits，每次敲掉指定位置的砖块；敲击之后，所有变得不稳定的砖块会立即消失。返回每次敲击导致掉落的砖块数量（不含被敲掉的那一块本身）。

「稳定」这个定义要翻译成图论语言：把第一行看成一个虚拟的「天花板」节点，那么一块砖稳定 $\iff$ 它与天花板连通。于是「敲掉一块砖后有多少砖掉落」就是「删除一个节点后，与天花板连通的节点数减少了多少」。

「不含被敲掉的那一块」这句话必须记牢。被敲的砖是主动移除的，不算掉落；但它在计数时又确实曾属于（或不属于）天花板连通块，所以最后要精确地把它扣掉一次。

还有一个容易忽略的情形：hits 里的位置可能本来就是空的（网格该处为 0）。这时候敲了个寂寞，答案是 0，且不能对结构做任何改动。题目保证 hits 中的位置互不相同，所以不必担心同一块砖被敲两次。

约束是 $1 \le m, n \le 200$、$1 \le hits \le 4 \times 10^4$。格子最多四万，敲击也最多四万。这个规模允许 $O(mn \cdot \alpha)$ 级别的做法，但不允许每次敲击后重跑一遍全图搜索——那是 $4 \times 10^4 \times 4 \times 10^4 = 1.6 \times 10^9$，必然超时。所以需要一个能增量维护连通性的结构。

边界方面：敲掉第一行的砖时，它自己不算掉落；敲掉一块孤立的、本来就不与天花板相连的砖时，掉落数为 0（它以及它带的那些砖其实在更早的时刻就已经掉了）。

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

核心思路

最直接的模拟是：每次敲掉一块砖，然后从第一行做一遍广度优先搜索，标记所有仍然稳定的砖，把没被标记的清除并计数。正确但太慢——$4 \times 10^4$ 次敲击乘以每次 $4 \times 10^4$ 个格子的搜索，量级到了 $10^9$。

瓶颈在于「删除」这个操作。并查集是维护连通性的利器，但它只支持合并、不支持分裂：一旦两个集合合并，就无法高效地再拆开。而敲砖块恰恰是在不断地拆散连通块。

突破口是时间倒流。把敲击序列反过来看：从「所有敲击都已完成」的最终状态出发，逆序地把砖一块块加回去。加回砖块只会让连通块合并，绝不会分裂——这正是并查集擅长的方向。这个「正向删除难、逆向添加易」的转换，是本题的全部精髓。

具体做法分三步。

第一步，构造终局。 复制一份网格，把 hits 中所有位置全部置 0，得到「所有敲击执行完毕」时的砖块分布。注意这里要用副本，原网格还要用来判断某次敲击的位置本来是否有砖。

第二步，在终局上建并查集，并引入虚拟顶部节点。 给每个格子编号 $r \times n + c$，再额外开一个编号为 $m \times n$ 的虚拟节点 top。把终局中所有第一行的砖与 top 合并，把所有四向相邻的砖两两合并。此后，「稳定的砖数」就等于 top 所在集合的大小减一（减掉 top 自身）。引入虚拟节点的好处是：把「与第一行任意一块砖连通」这个存在性条件，转化成了「与某个固定节点连通」，一次查询就能回答。

第三步，逆序加回砖块并作差。 对 $k$ 从最后一次敲击往前遍历：

若原网格该处本来就是 0，这次敲击没敲到任何东西，答案为 0，且不做任何结构改动，直接跳过。

否则，先记录当前 top 集合的大小 $prev$；把砖加回副本；若它在第一行就与 top 合并；再与四周所有存在的砖合并；最后记录新的大小 $cur$。

那么 $answer[k] = \max(0,\ cur - prev - 1)$。

这个式子要逐项解释。$cur - prev$ 是加回这块砖之后，与天花板连通的节点净增量。这些新增的节点包括：加回的那块砖本身，以及因为它的加入而重新接上天花板的所有砖。而后者，恰恰就是正向时间线上「敲掉这块砖时会掉落的那些砖」——两者是同一批砖，只是一个在加回时接上、一个在敲掉时脱落。所以减去 1（那块砖自己不算掉落）就是答案。

$\max(0, \cdot)$ 处理的是「加回的砖并没有连上天花板」的情形：此时 $cur - prev = 0$，式子给出 $-1$，需要修正为 0。物理含义是这块砖本来就悬空，敲掉它不会连累任何砖。

这里维持的不变量是：处理完第 $k$ 次逆序步骤后，副本网格与并查集所描述的，正是「第 $k$ 次敲击发生之前」的稳定状态。 正因为如此，第 $k$ 步的差值才准确对应第 $k$ 次敲击的后果。

并查集本身要按大小合并并做路径压缩，同时维护每个根节点的集合大小——后者是作差的数据来源，必须在 union 时同步更新。

解题步骤

第一步，复制网格并把 hits 中所有位置置 0，得到终局副本。 为什么必须是副本：原网格要保留用于判断「这次敲击处本来有没有砖」。若在原网格上就地置 0，这个信息就丢了，所有敲空的情形都会被误当成有效敲击。

第二步，建立大小为 $mn + 1$ 的并查集，末位下标 $mn$ 作为虚拟顶部。 为什么要虚拟顶部：稳定的判据是「与第一行某块砖连通」，这是一个对多个源点的存在性查询；接上虚拟节点后，它变成对单个节点的连通性查询，一次 find 即可，且集合大小天然就是稳定砖数（含虚拟节点）。

第三步，扫描终局副本，对每块砖：若在第一行就与顶部合并，再与上方、左方存在的砖合并。 为什么只看上和左：全表按行优先扫描时，右邻和下邻还没被访问到，等轮到它们时会反过来与当前格合并，所有相邻关系恰好被覆盖一次，不重不漏。

第四步，从最后一次敲击开始逆序遍历。 为什么必须逆序：并查集只能合并不能分裂，正序删除无法维护；逆序等价于把删除变成添加。

第五步，若原网格该处为 0，答案记 0 并跳过。 为什么不能只跳过而不判：如果照常执行「加回」，会凭空造出一块原本不存在的砖，副本网格从此与真实历史不符，后续所有差值全部作废。

第六步，记录 $prev = $ 顶部集合大小，把砖写回副本，视情况与顶部合并，再与四个方向上存在的砖合并，记录 $cur$。 为什么这里要查四个方向而不是像建图时只查两个：建图时是全表扫描，靠遍历顺序保证覆盖；这里是单点插入，必须主动检查全部四个邻居。为什么必须先写回副本再合并：若顺序反了，检查邻居时当前格还是 0，虽然不影响与邻居的合并（合并只依赖邻居的状态），但会让「当前格是否存在」的语义在中途不一致，后续步骤读到错误的副本状态。

第七步，令 $answer[k] = \max(0,\ cur - prev - 1)$。 为什么减 1：净增量里包含了加回的这块砖本身，而它不计入掉落数。为什么与 0 取最大：加回的砖若没连上天花板，净增量为 0，式子会得到 $-1$。

第八步，遍历结束返回答案数组。

以 grid = [[1,0,0,0],[1,1,1,0]]、hits = [[1,0]] 走一遍（$m = 2$、$n = 4$、虚拟顶部编号 8）。

构造终局：副本把 $(1,0)$ 置 0，得到 [[1,0,0,0],[0,1,1,0]]。

建图：扫描副本。$(0,0)$ 是砖且在第一行，与顶部合并，顶部集合变成 ${top, (0,0)}$，大小 2。$(1,1)$ 是砖，上邻 $(0,1)$ 为 0、左邻 $(1,0)$ 为 0，自成一个大小 1 的集合。$(1,2)$ 是砖，上邻 $(0,2)$ 为 0，左邻 $(1,1)$ 是砖，两者合并成大小 2 的集合。此时与天花板连通的只有 $(0,0)$ 一块砖——因为敲掉 $(1,0)$ 后，$(1,1)$ 和 $(1,2)$ 已经悬空。

逆序处理 $k = 0$：敲击位置是 $(1,0)$。原网格该处为 1，是一次有效敲击，继续。
记录 $prev = $ 顶部集合大小 $= 2$。
把 $(1,0)$ 写回副本，副本恢复成原始网格 [[1,0,0,0],[1,1,1,0]]。它不在第一行，所以不直接与顶部合并。
检查四个邻居：右邻 $(1,1)$ 是砖，合并——顶部集合此刻还没变，合并的是 $(1,0)$ 与 ${(1,1),(1,2)}$，得到大小 3 的集合；上邻 $(0,0)$ 是砖，合并——这一步把刚才那个大小 3 的集合接到了 ${top,(0,0)}$ 上，顶部集合变成 ${top,(0,0),(1,0),(1,1),(1,2)}$，大小 5；左邻列号为 $-1$ 越界，下邻行号为 2 越界，都跳过。
记录 $cur = 5$。
计算 $answer[0] = \max(0,\ 5 - 2 - 1) = 2$。

返回 [2]。核对物理含义：敲掉 $(1,0)$ 后，$(1,1)$ 和 $(1,2)$ 失去了唯一的支撑路径而掉落，共 2 块，而被敲掉的 $(1,0)$ 自身不计。净增量 3 里，1 块是加回的 $(1,0)$，另外 2 块正是掉落的那两块——这就是为什么减 1 之后恰好是答案。

再看一个体现 $\max(0, \cdot)$ 的例子：grid = [[1,0,0,0],[1,1,0,0]]、hits = [[1,1],[1,0]]，答案是 [0, 0]。终局副本是 [[1,0,0,0],[0,0,0,0]]，顶部集合为 ${top,(0,0)}$ 大小 2。逆序先处理 $k = 1$ 即 $(1,0)$：$prev = 2$，加回后与上邻 $(0,0)$ 合并，$cur = 3$，$answer[1] = \max(0, 3-2-1) = 0$——敲掉 $(1,0)$ 时它上方的 $(1,1)$ 已经被更早的敲击移走了，无砖可掉。再处理 $k = 0$ 即 $(1,1)$：$prev = 3$，加回后与左邻 $(1,0)$ 合并，$cur = 4$，$answer[0] = \max(0, 4-3-1) = 0$——敲掉 $(1,1)$ 时它是连通块的末端，不带走任何砖。

代码实现

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
}

复杂度分析

时间复杂度：$O\big((mn + hits ) \cdot \alpha(mn)\big)$。构造终局与初始建图各扫一遍全表，是 $O(mn)$ 次合并；逆序处理每次敲击最多做 5 次合并（四个方向加一个顶部），是 $O( hits )$ 次。并查集配合路径压缩与按大小合并，单次操作的均摊代价是反阿克曼函数 $\alpha$，实际可视为常数。$mn \le 4 \times 10^4$、$ hits \le 4 \times 10^4$，总量在十万级。相比「每次敲击重跑一遍广搜」的 $O(mn \cdot hits ) \approx 1.6 \times 10^9$，快了四个数量级。

空间复杂度：$O(mn)$。网格副本、并查集的父指针数组与大小数组各占 $O(mn)$。此外递归版的 find 在极端情况下有 $O(mn)$ 的栈深，但路径压缩会迅速把树压平，实际深度很小；若担心可以改写成迭代版。

关键点总结

并查集只能合并不能分裂，所以遇到删除就把时间倒过来。这是本题最值得带走的思想：正向的「删除节点、连通块分裂」无法增量维护，逆向的「添加节点、连通块合并」正好是并查集的原生操作。凡是看到「按顺序删除并查询连通性」，先想能不能离线倒序处理。

虚拟节点把「与一组源点连通」压成「与一个节点连通」。第一行有很多砖，逐个判断很麻烦；接上一个虚拟顶部之后，稳定性判定和稳定砖计数都变成对单个节点的查询。这个技巧在被围绕的区域、边界连通类题目里同样通用。

答案由集合大小的差值给出，而不是显式搜索。$cur - prev - 1$ 一步到位，既算出了掉落数，又避开了任何遍历。要用好它，前提是并查集在 union 时同步维护了每个根的集合大小——这个「顺带维护聚合量」的习惯，能让并查集回答远超连通性本身的问题。

保留原始输入用于区分「有效操作」与「无效操作」。hits 可能敲在空处，必须靠未被修改的原网格来判断。凡是要「先把某些位置清空再逆推」的题，都要留一份原始数据做参照。

减一与取最大值这两个修正各有明确的物理含义，不是凑答案：减一扣掉加回的砖自身，取最大值处理「这块砖压根没连上天花板」的情形。写出这类公式后要能逐项解释，否则边界一定会出错。

面试视角：这题的分水岭是能否说出「逆序把砖加回去」。开口先讲清楚「并查集不支持删除，所以我把敲击序列倒过来处理」，再讲虚拟顶部，最后给出差值公式并解释减一的来源——三步讲完，面试官基本就认可了。常见追问有三个：一是「为什么不能正向做」，答并查集无法分裂；二是「$-1$ 和 $\max(0,\cdot)$ 分别在处理什么」，要能各举一个用例；三是「如果 hits 里有重复位置怎么办」，答需要先去重或标记已处理，否则同一块砖会被加回两次导致计数错乱（本题的约束保证了位置互不相同）。

易错点总结

错误写法：正向处理敲击，每次敲完用并查集重新建图。以 $mn = 4 \times 10^4$、$ hits = 4 \times 10^4$ 的输入为例，每次重建都是 $O(mn)$，总量 $1.6 \times 10^9$，必然超时。并查集不支持删除，正向做只能靠重建，代价无法接受。

错误写法：忘记先把 hits 中的位置在副本里全部置 0 就开始建图。以 grid = [[1,0,0,0],[1,1,1,0]]、hits = [[1,0]] 为例，初始图里 $(1,0)$ 仍在，顶部集合大小是 5；逆序处理时 $prev$ 和 $cur$ 都是 5，$answer[0] = \max(0, -1) = 0$，而正确答案是 2。必须从「所有敲击都已完成」的终局出发。

错误写法：在原网格上就地置 0，不另存副本。以 hits 中含有一个本来就是空格的位置为例，原网格被改写后无法再判断「这次敲击是否有效」，空敲会被当成有效敲击执行「加回」，凭空造出一块不存在的砖，此后所有答案全部错位。

错误写法：漏掉 grid[r][c] == 0 的跳过判断。以 grid = [[1,0],[1,0]]、hits = [[0,1]] 为例，$(0,1)$ 本来就是空的，正确答案是 0；漏判会把它当砖加回并与顶部合并，$cur - prev = 1$，答案算成 $\max(0, 0) = 0$ 侥幸相同——但换成 hits = [[0,1],[1,1]] 这类连续空敲，两块虚构的砖会互相合并并连上顶部，答案变成非零，彻底错误。

错误写法：答案忘记减 1。以 grid = [[1,0,0,0],[1,1,1,0]]、hits = [[1,0]] 为例，$cur - prev = 3$，直接返回 3，而正确答案是 2——多算的那一块正是被敲掉的 $(1,0)$ 自己，它不计入掉落。

错误写法：不做 $\max(0, \cdot)$ 修正。以 grid = [[0,0],[1,1]]、hits = [[1,0]] 为例，这块砖本来就悬空（第一行全空），加回后与顶部无关，$cur - prev = 0$，式子给出 $-1$，返回负数。悬空砖被敲不会连累任何砖，答案应是 0。

错误写法：union 时不维护集合大小，或只更新被合并的一方。以任意输入为例，$getSize(top)$ 返回的值失真，差值计算完全失去意义。大小必须在每次真实合并（两个根不同）时累加到新根上，且路径压缩后要通过 find 拿根再读大小，不能直接读 size[top]。

错误写法：getSize 直接返回 size[top] 而不是 size[find(top)]。以顶部节点在某次合并中被挂到别人下面的情形为例（按大小合并时完全可能发生），size[top] 停留在旧值 1，所有差值都算成负数。查询集合大小必须先找根。

错误写法：逆序加回时只检查上、左两个方向。以 grid = [[1,1],[0,1]]、hits = [[0,1]] 为例，加回 $(0,1)$ 时需要与下邻 $(1,1)$ 合并才能把它拉进顶部集合；只查上左会漏掉这次合并，答案偏小。建图时靠扫描顺序覆盖了所有相邻关系，但单点插入必须主动查全部四个方向。

错误写法：先做合并再把砖写回副本。以两次敲击落在相邻格子的输入为例，后处理的那一格在检查邻居时，先处理的那一格若尚未写回副本，就会被当成空格而漏掉合并，两块砖没接上，顶部集合偏小。副本状态必须在合并之前更新到位。

错误写法：虚拟顶部的编号与某个真实格子冲突。以 $m = 2$、$n = 4$ 为例，格子编号是 0 到 7，虚拟顶部必须取 8；若误取 $m \times n - 1 = 7$，它会与格子 $(1,3)$ 混为一体，连通性判定彻底错乱。并查集的规模要开 $mn + 1$。

错误写法：认为顶部集合大小就是稳定砖数，忘记虚拟节点自身也占 1。以只有 $(0,0)$ 一块砖的网格为例，顶部集合大小是 2 而稳定砖只有 1 块。不过本题只用到大小的差值，虚拟节点的这个常数偏移会自动抵消——但如果你在别处直接用集合大小作为砖数输出，就会整体多一。

相似题目

题目	难度	考察点
305. 岛屿数量 II	困难	正向逐个加陆地并动态维护岛屿数，是本题「加回」操作的正序版本
130. 被围绕的区域	中等	同样用虚拟节点代表「边界」，把多源连通性压成单点查询
200. 岛屿数量	中等	静态一次性统计连通块，可用并查集也可用搜索，是网格连通性的入门题
827. 最大人工岛	困难	先给每个岛编号并记大小，再枚举每个空格试填，考察的是「预处理集合大小再查询」
547. 省份数量	中等	邻接矩阵直接给边的连通分量计数，可用来熟悉并查集模板
684. 冗余连接	中等	加边过程中检测首次成环，训练「合并前先判连通」的写法
1319. 连通网络的操作次数	中等	答案是连通分量数减一，同时要先判断边是否足够，是并查集计数的直接应用
1489. 找到最小生成树里的关键边和伪关键边	困难	反复用并查集跑带约束的最小生成树，训练「删边 / 强制加边」的离线处理思路