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

题目描述

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones，其中 stones[i] = [x_i, y_i] 表示第 i 块石头的位置，返回 最多 可以移除的石头个数。

示例 1：

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
1. 移除石头 [2,2]，因为它和 [2,1] 同列
2. 移除石头 [2,1]，因为它和 [0,1] 同行
3. 移除石头 [1,2]，因为它和 [1,0] 同列
4. 移除石头 [1,0]，因为它和 [0,0] 同行
5. 移除石头 [0,1]，因为它和 [0,0] 同列
剩下的石头是 [0,0]。

示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：移除 [2,2]、[2,0] 和 [0,2] 这三块石头之后，剩下两块石头 [0,0] 和 [1,1]。

提示：

• 1 <= stones.length <= 1000
• 0 <= x_i, y_i <= 10^4
• stones 中每个点都不相同

解题思路

问题分析

• 同一行或同一列只要有 >= 2 块石头，就可以不断移除。移除的条件是「同行或者同列上有其他石头存在」，也就是说只要处在一个行或列连通的集合里，除了最终保留的那一个，其余都能被移除。
• 如果把同一行的石头、同一列的石头都关联起来，就会形成若干个连通分量。在一个连通分量中，所有石头都通过行-列的连接互相可达，可以通过不断移除最终只留下1块石头。
• 因此，对于每个连通分量，最多能移除 size - 1 块，答案就是 n - (连通分量的个数)。

为什么用并查集

把每一块石头视作节点太多（n <= 1000）但也可行。更简洁的做法是将行和列也当成节点。注意行和列的编号可能重复（行号是 x，列号是 y），为了区分，用 x 表示行，用 y + 10005（或直接用 10^4 + y）表示列，或者直接用一个偏移量把列映射到不同的索引范围。

对于每一块石头 [x,y]，就把 row_node(x) 和 col_node(y) 合并。所有通过同行或同列相连的石头都会进入同一个并查集。

最后统计有多少个不同的根，这些根就是连通分量的数量。每个分量保留 1 块石头，其余移除。

实现要点

• 选用偏移：用 10000 作为列的偏移（题目中坐标 <= 10^4），row = x, col = y + 10000。
• 收集所有用到的节点（所有行和所有列），初始化并查集。
• 对每块石头 [x,y] 执行 merge(x, y + offset)。
• 用集合统计不同的根：对每块石头取 find(x) 或 find(y + offset) 加入集合，集合大小即连通分量数。
• 答案 = n - count_of_components。

完整代码实现

from typing import List

class UnionFind:
    def __init__(self, n):
        self.fa = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def merge(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.fa[ry] = rx
        self.size[rx] += self.size[ry]
        return True


class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        offset = 10005
        uf = UnionFind(10005 * 2)
        for x, y in stones:
            uf.merge(x, y + offset)
        roots = set()
        for x, y in stones:
            roots.add(uf.find(x))
        return n - len(roots)

示例推演

示例 1： stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

把行、列合并：

• (0,0) -> 合并行 0 和列 10005
• (0,1) -> 合并行 0 和列 10006（和前者同根）
• (1,0) -> 合并行 1 和列 10005（和行 0 同根）
• (1,2) -> 合并行 1 和列 10007
• (2,1) -> 合并行 2 和列 10006
• (2,2) -> 合并行 2 和列 10007

所有石头都连到同一个连通分量，连通分量数 = 1。答案 = 6 - 1 = 5，符合示例。

复杂度分析

解法	时间复杂度	空间复杂度	说明
并查集（最优）	O(n α(M))	O(M)	M = 20010，n <= 1000

易错点总结

• 行列重名要偏移：如果不用偏移，行号和列号相同会被当成同一个节点，合并关系就会出错。
• 并查集大小要够：坐标最大是 10^4，需要给列预留 offset + 10000 的范围，直接开 20010 足够。
• 统计根的对象：统计的是石头对应的根，而不是节点总数。用 set() 收集每块石头的 find(x)（或者 find(y+offset) 都可以，因为它们已被合并到同一根）。
• 保留数量：每个连通分量最终能保留 1 块石头，所以能移除 n - 分量数。

扩展思考

这道题的巧妙之处在于把「二维关系」降维成「一维并查集」。思路可以类比到「岛屿」「朋友圈」等问题：当元素之间通过多个维度建立联系时，可以把维度也映射为节点统一处理。