LeetCode 803. 打砖块

Categories:

题目描述
思路分析
1. 解法一：逆向并查集（推荐）
相似题目

题目描述

✅ 803. 打砖块

思路分析

解法一：逆向并查集（推荐）

核心思路：

正向删砖块很难维护连通性，改为逆向思维：将砖块按逆序”加回”，统计每次加入后顶部连通块大小的变化

建立并查集，新增一个虚拟顶部节点（编号 m*n），第一行所有砖块与虚拟节点相连

先将不在 hits 中的砖块加入并查集，再逆序将 hits 中的砖块加回，每次计算连通块大小变化即为该次打击掉落的砖块数

注意：同一位置可能被多次击打，需去重处理

复杂度分析：

时间复杂度：O((m×n + k) × α(m×n))，其中 m、n 为矩阵行列数，k 为打击次数，α 为并查集逆阿克曼函数

空间复杂度：O(m×n)，并查集所需空间

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

    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length;
        int n = grid[0].length;

        // 初始化并查集，虚拟顶部节点编号为 m*n
        parent = new int[m * n + 1];
        size = new int[m * n + 1];
        for (int i = 0; i <= m * n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        // 复制网格，先将所有被打击的砖块置为 0
        int[][] copy = new int[m][n];
        for (int i = 0; i < m; i++) {
            copy[i] = grid[i].clone();
        }
        for (int[] hit : hits) {
            copy[hit[0]][hit[1]] = 0;
        }

        // 将不被打击的砖块加入并查集
        int top = m * n;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (copy[i][j] == 1) {
                    if (i == 0) {
                        union(top, j, m, n, copy);
                    }
                    if (i > 0 && copy[i - 1][j] == 1) {
                        union(index(i, j, n), index(i - 1, j, n), m, n, copy);
                    }
                    if (j > 0 && copy[i][j - 1] == 1) {
                        union(index(i, j, n), index(i, j - 1, n), m, n, copy);
                    }
                }
            }
        }

        int[] result = 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 prevTop = size[find(top)];
            copy[r][c] = 1;

            // 第一行与虚拟顶部相连
            if (r == 0) {
                union(index(r, c, n), top, m, n, copy);
            }

            // 与四个方向的砖块合并
            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && copy[nr][nc] == 1) {
                    union(index(r, c, n), index(nr, nc, n), m, n, copy);
                }
            }

            int currTop = size[find(top)];
            result[k] = Math.max(0, currTop - prevTop - 1);
        }

        return result;
    }

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

    private void union(int x, int y, int m, int n, int[][] copy) {
        int px = find(x);
        int py = find(y);
        if (px == py) {
            return;
        }
        if (size[px] < size[py]) {
            parent[px] = py;
            size[py] += size[px];
        } else {
            parent[py] = px;
            size[px] += size[py];
        }
    }

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[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 }

    // 复制网格，将所有打击位置置为 0
    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
}

相似题目

题目	难度	考察点
547. 省份数量	中等	并查集
684. 冗余连接	中等	并查集
1319. 连通网络的操作次数	中等	并查集
200. 岛屿数量	中等	并查集/DFS
1020. 飞地的数量	中等	DFS/BFS
305. 岛屿数量 II	困难	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/23455823