LeetCode 947. 移除最多的同行或同列石头

2026-09-13 HGNULB 约 6 分钟

文章信息 2 个分类 4 个标签

分类

LeetCode 中等

题目描述

✅ 947. 移除最多的同行或同列石头

题意分析

只有当平面上仍存在另一块同行或同列的石头时，才能移除当前石头，求最多能移除多少块。把每块石头看成节点，同行或同列就连边；两块石头即使没有直接连边，也可能通过其他石头间接连通。

解法：按行列代表合并石头

核心思路

[!blue]

先看一个初始连通块。它至少要留下一块石头：当块内只剩最后一块时，同一块里的其他石头已经消失，而块外原本就没有与它同行或同列的石头，所以最后一块不能再移除。若共有 components 个连通块，最多只能移除 n - components 块。

这个数量一定能达到。在每个连通块中选一棵生成树和一个保留的根，从叶子向根依次删除非根节点。删除某个节点时，它的父节点还在，且树边表示二者同行或同列，所以每次删除都合法。最终恰好留下根，含 s 块石头的连通块可以移除 s - 1 块，所有块相加就是上述答案。

因此只需统计连通块，无需实际模拟删除。以石头下标作为并查集节点，并用 rows、columns 分别保存每一行、每一列中已经出现过的一块代表石头。遇到新石头时，若同行代表存在，就与它合并；同列也同样处理。

同一行的石头不必两两连边，全部连到一个代表就已经互相连通；同一列也一样。这些连接本身都是真实的同行或同列关系，因此既不会漏掉连通性，也不会错误地连接原本无关的块。代表只需是该行列中的某个石头下标，不必始终等于并查集根，find 会定位它当前所属的集合。

components 初始为 n，只有合并两个不同集合时才减一。行连接与列连接可能重复连接已经相通的石头，union 通过比较根返回是否确实完成合并，避免重复扣减。按大小合并与路径压缩只改变集合的内部表示，不改变连通关系。

解题步骤

为每块石头创建独立集合，令父节点指向自身、集合大小为 1，连通块数为 n。

顺序处理石头，分别查询它的行号和列号。

某行或列尚无代表时记录当前下标；已有代表时调用 union，只有返回成功才减少连通块数。

union 先查找两个根，根相同就不做修改；否则把较小集合接到较大集合，并更新大小。

全部石头处理完后返回 n - components。孤立石头始终单独成块，自然不能贡献可删除数量。

代码实现

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

    public int removeStones(int[][] stones) {
        int n = stones.length;
        int components = n;

        parent = new int[n];
        size = new int[n];

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

        Map<Integer, Integer> rows = new HashMap<>();
        Map<Integer, Integer> columns = new HashMap<>();

        for (int i = 0; i < n; i++) {
            Integer row = rows.putIfAbsent(stones[i][0], i);
            Integer col = columns.putIfAbsent(stones[i][1], i);

            if (row != null && union(i, row)) {
                components--;
            }

            if (col != null && union(i, col)) {
                components--;
            }
        }

        return n - components;
    }

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

        return x;
    }

    private boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) {
            return false;
        }

        if (size[a] < size[b]) {
            int t = a;

            a = b;
            b = t;
        }

        parent[b] = a;
        size[a] += size[b];

        return true;
    }
}

func removeStones(stones [][]int) int {
    n := len(stones)
    components := n
    parent, size := make([]int, n), make([]int, n)
    for i := range parent {
        parent[i] = i
        size[i] = 1
    }
    find := func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    union := func(a, b int) bool {
        a, b = find(a), find(b)
        if a == b {
            return false
        }
        if size[a] < size[b] {
            a, b = b, a
        }
        parent[b] = a
        size[a] += size[b]
        return true
    }
    rows, columns := map[int]int{}, map[int]int{}
    for i, stone := range stones {
        if j, ok := rows[stone[0]]; ok {
            if union(i, j) {
                components--
            }
        } else {
            rows[stone[0]] = i
        }
        if j, ok := columns[stone[1]]; ok {
            if union(i, j) {
                components--
            }
        } else {
            columns[stone[1]] = i
        }
    }
    return n - components
}

复杂度分析

时间复杂度：期望 $O(n\alpha(n))$。每块石头只进行常数次哈希查询，最多触发两次合并；路径压缩与按大小合并使并查集操作的摊还开销为 $O(\alpha(n))$。

空间复杂度：$O(n)$，父节点、集合大小和两个行列代表映射都至多保存线性数量的元素。

关键点总结

[!green]

每个连通块至少留一块，按生成树从叶到根删除又能只留一块，因此答案恰好是总数减连通块数。

每行、每列只连一个代表即可保持完整连通性，不需要枚举所有石头对。

集合数只随成功合并减少，连接尝试次数不等于减少的集合数。

易错点总结

[!yellow]

两块石头已在同一集合时，不能再次减少连通块数。

行号和列号要分别记录，不能把数值相同的行坐标与列坐标当成同一种连接。

不能只统计直接同行同列的分组，还必须合并经其他石头形成的间接连通关系。

随意模拟删除可能先破坏连接，连通块公式依赖的是存在从叶到根的合法删除顺序。

行列代表不必随着并查集根变化而更新，但合并前必须通过 find 取得当前根。

相似题目

题目	难度	关联与区别
547. 省份数量	中等	同样统计连通块；本题的答案进一步利用每块只需保留一块石头的证明。
684. 冗余连接	中等	复用并查集合并失败的判断，防止已经连通时重复减少集合数量。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/95648769

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！