题解 | 打砖块

题干解析

题设给定一个砖块状态数组和每次的敲击情况，砖块只有互相在上下左右具备连接，且有至少一个砖块与顶部连接才算稳定，打击后变得不稳定的砖块组会被消除，要求我们返回每次敲击后的砖块因不稳定而消除的数量。

算法思路

初始情况所有还存在的砖块可看作一个组，后续的击打便是消除组内部分连接边使得组可能一分为二也可能不变，一分为二时不稳定的组便会被清除，且需要确定清除了多少个砖块。

有关分组的数据我们不妨使用并查集进行维护，但有一个重要问题便是并查集本身并不支持删除已建立的连接。对此我们不妨逆向解决此问题，由此我们成功将并查集无法处理的边删除问题逆向为边增添的问题。假设我们得到所有需要打掉的砖块后的砖块状态，并以此状态作为基准建立并查集（同时维护各组砖块数量）。然后逆序增添被打掉的砖块，如果并查集中稳定组的大小发生明显变化则证明打掉砖块后有因不稳定而被消除的砖块组。我们记录稳定组前后的大小变化便可推断出本次消除的砖块数量。

实现代码

class L803 {
    class UnionFind {
        vector<int> parent;
        vector<int> rank; // 秩（树高度近似值）
        vector<int> size; // 各集的大小

    public:
        explicit UnionFind(const int n) : parent(n), rank(n, 0), size(n, 1) {
            iota(parent.begin(), parent.end(), 0); // 初始化
        }

        int find(int x) {
            // 迭代路径压缩（更节省栈空间）
            while (parent[x] != x) {
                parent[x] = parent[parent[x]]; // 路径减半压缩
                x = parent[x];
            }
            return x;
        }

        void unite(const int x, const int y) {
            const int rootX = find(x);
            const int rootY = find(y);

            if (rootX == rootY) return;

            // 按秩合并：小树挂到大树
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX]; // 主要加载方向：rootY成为最新的根，下同
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
                rank[rootX]++; // 高度相同才增加
            }
        }

        bool isConnected(const int x, const int y) {
            return find(x) == find(y);
        }

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

public:
    vector<int> hitBricks(vector<vector<int> > &grid, vector<vector<int> > &hits) {
        const int n = static_cast<int>(grid.size()), m = static_cast<int>(grid[0].size());
        vector<int> ans(hits.size(), 0);
        UnionFind uf(n * m + 1); // 并查集（与n * m相连的组即为稳定组）
        vector<vector<int> > fin = grid; // 结束时棋盘
        for (auto hit: hits) fin[hit[0]][hit[1]] = 0;
        // 构建并查集
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (fin[i][j]) {
                    if (!i) uf.unite(n * m, i * m + j); // 稳定组
                    else {
                      	// 类BFS
                        if (fin[i - 1][j]) uf.unite(i * m + j, (i - 1) * m + j);
                        if (j && fin[i][j - 1]) uf.unite(i * m + j, i * m + (j - 1));
                        if (i + 1 < n && fin[i + 1][j]) uf.unite(i * m + j, (i + 1) * m + j);
                        if (j + 1 < m && fin[i][j + 1]) uf.unite(i * m + j, i * m + (j + 1));
                    }
                }
            }
        }
        // 逆序计算答案
        vector<pair<int, int> > dir = {
            {0, 1}, {0, -1}, {1, 0}, {-1, 0}
        };
        for (int i = static_cast<int>(hits.size() - 1); i >= 0; --i) {
            const int r = hits[i][0], c = hits[i][1];
            if (!grid[r][c]) continue; // 没打到砖块

            const int start = uf.getSize(n * m); // 初始砖块数

            if (!r) uf.unite(c, n * m); // 并首行砖块
            for (auto [dr, dc]: dir) {
                const int r_ = r + dr, c_ = c + dc;
                if (r_ >= 0 && r_ < n && c_ >= 0 && c_ < m && fin[r_][c_])
                    uf.unite(r * m + c, r_ * m + c_);
            }
            const int end = uf.getSize(n * m); // 结束砖块数
            ans[i] = max(0, start - end - 1);
            fin[r][c] = 1;
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：并查集每次查询耗时为，构建并查集过程中总计最多查询次数为，逆向求解每次查询次数为， 与均为常数，总记时间复杂度为，其中k为击打砖块的次数，为阿克曼函数的反函数，可以认为是一个很小的常数。
• 空间复杂度：主要空间消耗为维护并查集所需的三个数组，总空间复杂度为