# 0947. 移除最多的同行或同列石头 ### 题目地址 (947. 移除最多的同行或同列石头） ### 题目描述 ``` 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 <= 1000 0 <= xi, yi <= 104 不会有两块石头放在同一个坐标点上 ``` ### 前置知识 * [并查集](/leetcode-solution/thinkings/union-find.md) ### 思路 读完题目之后， 看了下数据范围。我猜测可能和动态规划什么的有关，**而且时间复杂度是 $O(n^2)$ 左右**，其中 n 为 stones 的长度。继续看了下示例，然后跟着思考了一下，发现很像是某种联通关系。 类似的题目有很多，题目描述记不太清楚了。大概意思是给你一个二维网格，行和列需要**一起增加**，求最小和什么的。这类题目都是行和列具有某种绑定关系。 于是我想到了使用并查集来做。 后面想了一下，反正就是**求联通区域的个数**，因此使用 DFS 和 BFS 都可以。如果你想使用 DFS 或者 BFS 来解，可以结合我之前写的 [小岛专题](/leetcode-solution/thinkings/island.md) 练习一下哦。 继续分析下题目。 题目的意思是任意一个石头可以消除和它同行和同列的其他石子。于是我就想象出了下面这样一幅图，其中红色的方块表示石子，方块的连线表示离得最近的可以消除的石子。实际上，一个石子除了可以消除图中线条直接相连的石子，还可以消除邻居的邻居。**这提示我们使用并查集维护这种联通关系**，联通的依据自然就是列或者行一样。 ![](https://p.ipic.vip/0g23sy.jpg) 上面是一个全联通的图。如下是有两个联通域的图。 ![](https://p.ipic.vip/9ysm39.jpg) 有了上面的知识，其实就可以将石子全部建立并查集的联系，并计算联通子图的个数。答案就是 n - 联通子图的个数，其中 n 为 stones 的长度。 核心代码： ```py 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 ``` 有的人想问，这可行么？即**我可以将一个联通子图的石子移除只剩下一个么？** 答案是肯定的。其实上面我提到了这道题也可使用 DFS 和 BFS 的方式来做。如果你使用 DFS 的方式来做，会发现其实 **DFS 路径的取反就是消除的顺序**，当然消除的顺序不唯一，因为遍历访问联通子图的序列并不唯一。 如果题目要求我们求移除顺序，那我们可以考虑使用 DFS 来做，同时记录路径信息即可。 ![](https://p.ipic.vip/b62ori.jpg) 使用遍历的方式（BFS 或者 DFS），由于每次访问一个石子都需要使用 visited 来记录访问信息防止环的产生，因此 visited 的逆序也是一个可行的移除顺序。不过这要求你的 visited 的是有序的。实现的方法有很多，有点偏题了，这里就不赘述了。 实际上，上面的并查集代码仍然可以优化。上面的思路是直接将点作为并查集的联通条件。实际上，我们可以将点的横纵坐标分别作为联通条件。即如果横坐标相同的联通到一个子图，纵坐标相同的联通到一个子图。如下图： ![](https://p.ipic.vip/z3q3o8.jpg) 为了达到这个模板，我们不能再初始化的时候计算联通域数量了，即不能像上面那样 `uf = UF(n)`（此时联通域个数为 n）。因为横坐标，纵坐标分别有多少不重复的我们是不知道的，一种思路是先计算出**横坐标，纵坐标分别有多少不重复的**。这当然可以，还有一种思路是在 find 过程中计算，这样 one pass 即可完成，具体见下方代码区。 由于我们需要**区分横纵坐标**（上面图也可以看出来），因此可**用一种映射**区分二者。由于题目限定了横纵坐标取值为 10000 以内（包含 10000），一种思路就是将 x 或者 y 加上 10001。 核心代码： ```py n = len(stones) uf = UF(0) for i in range(n): uf.union(stones[i][0] + 10001, stones[i][1]) return n - uf.cnt ``` ### 代码 #### 并查集 代码支持： Python3 其中 `class UF` 部分是标准的无权并查集模板，我一行代码都没变。关于模板可以去 [并查集](/leetcode-solution/thinkings/union-find.md) 查看。 ```python class UF: def __init__(self, M): self.parent = {} self.cnt = 0 # 初始化 parent，size 和 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 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 ``` **复杂度分析** 令 n 为数组 stones 的长度。 * 时间复杂度：$O(n^2logn)$ * 空间复杂度：$O(n)$ #### 优化的并查集 代码支持： Python3 ```py 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 ``` **复杂度分析** 令 n 为数组 stones 的长度。 * 时间复杂度：$O(nlogn)$ * 空间复杂度：$O(n)$ #### DFS 代码支持： Java > by 一位不愿透露姓名的热心网友。 ```java public int removeStones(int[][] stones) { Set visit = new HashSet(); int count = 0; int offset = 10000; HashMap >map = new HashMap(); // 构造图 每一项是一个节点 for (int i = 0; i < stones.length; i++) { int [] node = stones[i]; List list = map.getOrDefault(node[0]-offset,new ArrayList<>()); list.add(node); map.put(node[0]-offset,list); List 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 >map){ int offset = 10000; List 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 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)$ 力扣的小伙伴的点下我头像的关注按钮，这样就会第一时间收到我的动态啦\~ 以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 38K star 啦。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/947.most-stones-removed-with-same-row-or-column.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.