0947. Most Stones Removed with Same Row or Column

题目信息

题号:

0947

难度:

Medium

主题:

平面点集、连通关系、最大移除数

原题:

LeetCode 0947

重点:

每次只能移除仍与另一块剩余石头同行或同列的石头;操作顺序可自由选择,目标是最大化总移除数

题目重述

给定二维平面上互不重合的石头坐标数组 stones。一次操作可以移除一块石头,但移除时必须仍有另一块未被移除的石头与它拥有相同横坐标或相同纵坐标。

可以按任意顺序反复执行操作。请返回最多能够移除多少块石头。最后留下的石头不需要满足任何额外条件。

1 <= stones.length <= 1000,0 <= x_i, y_i <= 10^4,坐标互不相同。

自建示例

一个连通簇和一块孤立石头:

输入:stones = [[0,0],[0,2],[2,0],[3,3]]
输出:2
解释:前三块石头通过同行或同列关系连成一组,可移除其中两块并保留一块;[3,3] 与其他石头不同行也不同列,无法移除。

只有一块石头:

输入:stones = [[4,7]]
输出:0
解释:不存在另一块同行或同列的剩余石头,因此唯一石头不能被移除。