- 文档
- 教程
- 知识库
【免费下载链接】leetcode
LeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)
本篇题解围绕 LeetCode 947「移除最多的同行或同列石头」展开，讲解如何把「同行 / 同列可互相移除」的规则抽象为联通分量问题，并给出基础并查集、优化并查集与 DFS 三种完整可运行解法及其复杂度分析。读完本文，你将掌握「连通性」类题目的通用建模思路（并查集计数联通分量、坐标偏移映射、懒初始化等技巧），并能直接套用于仓库 并查集专题 与 小岛问题专题 中的同类题目。
题目描述
n 块石头放置在二维平面中的一些整数坐标点上，每个坐标点上最多只能有一块石头。如果一块石头的同行或者同列上有其他石头存在，那么就可以移除这块石头。给你一个长度为 n 的数组stones，其中stones[i] = [xi, yi]表示第 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 解释：一种移除 3 块石头的方法如下所示： 1. 移除石头 [2,2] ，因为它和 [2,0] 同行。 2. 移除石头 [2,0] ，因为它和 [0,0] 同列。 3. 移除石头 [0,2] ，因为它和 [0,0] 同行。 石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。示例 3：
输入：stones = [[0,0]] 输出：0 解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。提示：
1 <= stones.length <= 10000 <= xi, yi <= 10^4- 不会有两块石头放在同一个坐标点上
前置知识
- 并查集（Union-Find）
思路分析
读完题目后观察数据范围（n 最大 1000），可以猜测时间复杂度大约在 $O(n^2)$ 量级。进一步分析示例会发现：题目描述的「同行 / 同列可互相移除」本质上是一种联通关系——一块石头不仅能移除与它直接同行同列的石头，还能通过「邻居的邻居」一路传导下去。这类「行和列具有某种绑定关系」的题目，正是并查集的典型应用场景，核心目标就是求联通区域的个数。
把问题抽象为联通分量
将每块石头看作图中的一个节点，若两块石头同行或同列，则在二者之间连一条边。这样所有石头会被划分成若干联通分量（连通子图）。可以证明：一个联通分量内，最多只能剩下 1 块石头，其余都可以被移除。因此答案为：
答案 = n - 联通分量的个数其中 n 为 stones 的长度。例如示例 1 的 6 块石头全部连成一个联通分量，故答案是6 - 1 = 5；示例 2 的 5 块石头分为两个联通分量（[0,0],[0,2],[2,0],[2,2]一组、[1,1]单独一组），故答案是5 - 2 = 3。
为什么一个联通分量能且只能剩一块石头？
「能」的论证：使用 DFS / BFS 遍历一个联通分量，访问顺序本身对应一条「有效移除序列」。因为每次访问到的节点在访问时必然与已访问节点同行或同列（正是通过这条边到达的），所以访问路径的逆序（或有序 visited 记录的逆序）就是一个可行的移除顺序，最终只留下遍历的起点。这个论证同样说明 DFS / BFS 可以求解本题：若题目进一步要求输出移除顺序，用 DFS 记录路径即可。
「只能」的论证：若一个联通分量内剩余 2 块及以上石头，则移除动作意味着最后留下的石头必须与某块被移除的石头同行或同列，这与「联通分量」的闭合性矛盾——被移除石头的同行同列关系必然把残留石头连回该分量。因此每分量最多留 1 块，答案即n - 联通分量数。
并查集解题主线
- 基础版：将 n 块石头两两合并，合并条件为「行相同或列相同」，最后统计联通分量个数
uf.cnt。 - 优化版：不再以石头为节点，而是把横坐标、纵坐标分别作为节点（用偏移量区分二者），每块石头只需一次
union，联通分量个数在find过程中惰性统计。 - DFS / BFS 版：把行、列映射为图的顶点建图，然后统计联通分量个数。
解法一：基础并查集（两两合并石头）
并查集模板回顾
本题所用的class UF是仓库 并查集专题 中的标准无权并查集模板。其核心 API 如下：
find(x)：返回 x 所在集合的代表（根）。递归实现中同时完成路径压缩，把查找路径上的节点直接挂到根上，将树高压低，避免 find 退化为 $O(n)$；union(p, q)：若 p、q 不联通，则将其中一个根挂到另一个根上，并使联通分量计数cnt减 1；connected(p, q)：判断 p、q 是否联通，即find(p) == find(q)。
仓库模板中还展示了带size的按秩（按大小）合并：总是把较小的树挂到较大的树上，使树尽量平衡，配合路径压缩后单次操作复杂度趋近 $O(1)$（严格说是阿克曼函数反函数量级）。本题两两合并写法省去按秩合并以突出主脉络，两者均正确。
代码（Python3）
class UF: def __init__(self, M): self.parent = {} self.cnt = 0 # 初始化 parent 和 cnt for i in range(M): self.parent[i] = i self.cnt += 1 def find(self, x): if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return leader_p = self.find(p) leader_q = self.find(q) self.parent[leader_p] = leader_q self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) class Solution: def removeStones(self, stones: List[List[int]]) -> int: n = len(stones) uf = UF(n) # 两个 for 循环将石头两两合并 for i in range(n): for j in range(i + 1, n): # 如果行或者列相同，将其联通成一个子图 if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]: uf.union(i, j) return n - uf.cnt初始化时每个石头各自为一个联通分量（cnt = n），每次合并使cnt减 1，最终n - uf.cnt即最多可移除数量。
复杂度分析
令 n 为数组 stones 的长度：
- 时间复杂度：$O(n^2 \log n)$（两两枚举 $O(n^2)$ 次，每次 union/find 受路径压缩影响，近似 $O(\log n)$ 以内）；
- 空间复杂度：$O(n)$（parent 哈希表存储 n 个节点）。
解法二：优化并查集（坐标映射 + 懒初始化）
优化动机
解法一将「石头」作为联通节点，需要两两枚举，复杂度为 $O(n^2)$。实际上，横坐标相同或纵坐标相同才是联通条件，因此可以反过来把横坐标、纵坐标分别作为节点：横坐标相同的石头共享一个「行节点」，纵坐标相同的共享一个「列节点」，每块石头只需把它的行节点与列节点合并一次，即可把所有同行同列的石头串进同一联通分量。
用偏移量区分横纵坐标
由于题目限定横纵坐标取值在0 <= xi, yi <= 10^4（含 10000），行节点与列节点的取值范围存在重叠（都是 0~10000）。为区分二者，将横坐标统一加上偏移量10001（即大于坐标上限 10001 即可，保证x + 10001永不与任何y值冲突），于是每个节点编号唯一：
- 行节点编号：
x + 10001 - 列节点编号：
y
例如石头[0, 0]即合并节点10001与0。
懒初始化的 find
优化版中不能像基础版那样在构造时预先统计联通分量数（因为横、纵坐标的不重复个数事先未知）。解决方式是在 find 过程中惰性创建节点：当x尚未出现在 parent 中时，令parent[x] = x并让cnt += 1，随后正常走路径压缩；union 合并成功时cnt -= 1。这样一遍union循环即可完成全部统计，实现 one-pass。
代码（Python3）
class UF: def __init__(self, M): self.parent = {} self.cnt = 0 def find(self, x): if x not in self.parent: self.cnt += 1 self.parent[x] = x if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return leader_p = self.find(p) leader_q = self.find(q) self.parent[leader_p] = leader_q self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) class Solution: def removeStones(self, stones: List[List[int]]) -> int: n = len(stones) uf = UF(0) for i in range(n): uf.union(stones[i][0] + 10001, stones[i][1]) return n - uf.cnt注意：这里的cnt统计的是「横纵坐标联通分量」的个数。为什么n - uf.cnt仍是答案？因为每块石头把它的行节点与列节点连在一起，每个石头联通分量恰对应一个「行/列互达」的联通块，其内石头数量减 1 即为可移除数，累加所有联通块即n - uf.cnt。这与解法一的结论一致。
复杂度分析
令 n 为数组 stones 的长度：
- 时间复杂度：$O(n \log n)$（只需一次遍历，每次 union 近似 $O(\log n)$ 以内，配合路径压缩趋近常数）；
- 空间复杂度：$O(n)$（parent 哈希表最多存储 2n 量级的节点，即每块石头贡献一个行节点和一个列节点）。
解法三：DFS 遍历联通分量（Java）
除了并查集，本题也可用 DFS / BFS 求解（思路与仓库 小岛问题专题 一脉相承：从每个未访问节点出发遍历整个联通分量，计数加一）。由于本题的「相邻」关系定义在行、列上，需要把行、列号映射为图的顶点：x - 10000表示行顶点，y表示列顶点，每块石头作为一条连接行顶点与列顶点的边；建图完成后，统计联通分量个数即可。
代码（Java）
public int removeStones(int[][] stones) { Set visit = new HashSet(); int count = 0; int offset = 10000; HashMap<Integer, List<int[]>> map = new HashMap(); // 构造图：行/列作为图的顶点，每块石头连接其行顶点与列顶点 for (int i = 0; i < stones.length; i++) { int[] node = stones[i]; List<int[]> list = map.getOrDefault(node[0] - offset, new ArrayList<>()); list.add(node); map.put(node[0] - offset, list); List<int[]> list1 = map.getOrDefault(node[1], new ArrayList<>()); list1.add(node); map.put(node[1], list1); } // 寻找联通分量 for (int i = 0; i < stones.length; i++) { int[] node = stones[i]; if (!visit.contains((node))) { visit.add((node)); dfs(node, visit, map); count++; } } return stones.length - count; } // 遍历节点 public void dfs(int[] node, Set set, HashMap<Integer, List<int[]>> map) { int offset = 10000; List<int[]> list = map.getOrDefault(node[0] - offset, new ArrayList<>()); for (int i = 0; i < list.size(); i++) { int[] item = list.get(i); if (!set.contains((item))) { set.add((item)); dfs(item, set, map); } } List<int[]> list2 = map.getOrDefault(node[1], new ArrayList<>()); for (int i = 0; i < list2.size(); i++) { int[] item = list2.get(i); if (!set.contains((item))) { set.add((item)); dfs(item, set, map); } } }复杂度分析
令 n 为数组 stones 的长度：
- 时间复杂度：建图与遍历图的时间均为 $O(n)$；
- 空间复杂度：$O(n)$（邻接表存储所有石头节点）。
三种解法对比
| 解法 | 建模方式 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 基础并查集 | 石头两两合并，合并条件为同行/同列 | $O(n^2 \log n)$ | $O(n)$ | n 较小、思路最直白 |
| 优化并查集 | 横/纵坐标分别作为节点，偏移量区分，懒初始化 | $O(n \log n)$ | $O(n)$ | n 较大时的首选 |
| DFS（BFS） | 行/列为顶点建图，统计联通分量 | $O(n)$ | $O(n)$ | 需要进一步输出移除顺序时可扩展记录路径 |
三种解法的正确性都建立在同一数学结论之上：答案 = n − 联通分量个数。并查集通过「合并」隐式维护联通分量，DFS/BFS 通过「遍历」显式划分联通分量，殊途同归。
与仓库其他题目的联系
本题是「连通性」类题目的代表性应用，可与仓库中以下内容对照练习：
- 并查集专题（union-find）：含背景、核心 API、路径压缩、按秩合并、带权并查集模板与复杂度分析，是本题模板的出处；
- 小岛问题专题（island）：DFS / BFS 求联通分量的通用套路与模板，可配合本题解法三练习；
- 同属「求联通分量个数」的并查集题目：547. 省份数量、839. 相似字符串组、959. 由斜杠切分区域；
- 并查集其他应用：721. 账户合并（等价类合并）、5936. 引爆最多的炸弹（联通分量计数）、3108. 带权图最小代价行走（带权联通性）、1168. 水资源分配优化（并查集 + 最小生成树思想）、1697. 检查边长度限制的路径是否存在（离线 + 并查集）。
总结
解 LeetCode 947 的关键在于识别题目背后的联通关系：同行 / 同列的石头构成联通分量，每分量最多保留一块石头，答案即n − 联通分量数。实现上，基础并查集思路直观；优化版通过「坐标 + 偏移量映射 + 懒初始化 find」把复杂度从 $O(n^2 \log n)$ 降到 $O(n \log n)$，是面试中值得重点掌握的进阶写法；DFS / BFS 版本则在需要输出移除顺序的场景下更具扩展性。遇到「连通、等价、互相可达」类题目时，优先联想并查集，并注意使用路径压缩（必要时空闲时配合按秩合并），可显著降低出错率与运行时间。
- 文档
- 教程
- 知识库
【免费下载链接】leetcode
LeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)
相关推荐
LeetCode-Go 题解：947. Most Stones Removed with Same Row or Column——并查集建模与行列映射优化实战
LeetCode Go 题解：947. Most Stones Removed with Same Row or Column——并查集建模与行列映射优化实战
示例工程LeetCode 1579 题解：并查集删除最多边保持图完全可遍历（LeetCode-Go 实现）
LeetCode 1579 题解：并查集删除最多边保持图完全可遍历（LeetCode Go 实现） 本篇技术指南以 LeetCode 第 1579 题《Remo
示例工程LeetCode 721. Accounts Merge 并查集解法详解：用 Go 合并同一用户的邮箱账户
LeetCode 721. Accounts Merge 并查集解法详解：用 Go 合并同一用户的邮箱账户 本文围绕 LeetCode 721 题《Accoun
示例工程
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
