继续并查集！
题目
打砖块
有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
示例1
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：
网格开始为：
[[1,0,0,0]，
[1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
[0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
[0,0,0,0]]
因此，结果为 [2] 。
示例2
输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：
网格开始为：
[[1,0,0,0],
[1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
[1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0],
[1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
[0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。
分析
一开始我的想法有点跑偏，从正向考虑，想通过并查集给每个分量维护一个屋顶连接数，然后打掉砖块的时候这个连接数减一，然后在遍历分量去搜索连接数为0的分量做统计，但是这么做代码越写越复杂，最后还是放弃了，采用了官方的逆向的思路。
题目拆解
正向拆解
1、有一个矩阵存放了若干个分量，标记为1代表此处有链接，标记为0代表此处无连接；
2、从屋顶开始走，如果可以走到某一个分量，该分量和屋顶相连，不会掉落；
3、每次进行一次敲击动作，检查有多少个分量失去了与屋顶的链接，返回这个数量；
简单来说，题目就是这三步，从题目正向来看，是一个把连通树，不断拆解的过程，每次敲击，要对原有的树进行一次拆分，看看拆分后，原有树还有多少个分量。
但是，并查集的主要能力是
合并和查找
，所以拆分并不是并查集这种数据结构擅长的能力。不过如果反过来想，我们先把敲击动作全部执行完，然后往回一步一步复原原本的树，这样的操作就是一个合并的操作，也就得到了并查集擅长的连通性判断的领域。
以这个思路重新拆解一下题目
逆向拆解
1、有一个矩阵存放了若干个分量，标记为1代表此处有链接，标记为0代表此处无连接；
2、从屋顶开始走，如果可以走到某一个分量，该分量和屋顶相连，不会掉落；
3、
每次在矩阵中进行一次粘合操作，检查粘合后，有多少个分量因为这次粘合而被链接到了屋顶。
逆向拆解之后，题目就变得清晰很多。
继续进行解题步骤的分析
分析步骤
1、整个矩阵所有点可以看做是一个链接到屋顶的树，本次并查集只有一个树。
2、矩阵中的每一个点都是一个分量，额外定义一个分量用来标记屋顶。
3、合并操作前置有二，1）如果在第一排，需要和屋顶合并；2）相连的分量进行合并
4、为分量添加一个连接数属性，标识以当前分量为根节点的分量有多少。
5、每次合并操作后，以屋顶为根节点的分量增加了多少，即代表经过本次粘合动作新增了多少分量。
解题步骤
1、定制并查集，增加
以当前分量为根节点的分量总数
属性
2、复制一个矩阵，执行所有的hit操作，得到一个最终矩阵，即为逆向的初始矩阵。
3、初始化并查集，将逆向的初始矩阵进行合并操作
4、每次粘合一个连接点，判断是否需要合并操作并执行。
5、获取合并前后与屋顶链接的分量总数，做差并记录结果。
代码实现
并查集构建
class HitBricksUnionFind {
// 存储连分量
protected int[] id;
// 当前并查集不同的连通分量总数
protected int count;
// 分量权重数组,数组里的值代表当前分量下的分量数量
private int[] weightArr;
public HitBricksUnionFind(int n) {
// 初始化时,没个分量互不连通
this.count = n;
// 初始化一个容纳全量分量的数组
this.id = new int[n];
for (int i = 0; i < n; i++) {
// 没个分量初始值指向自身
id[i] = i;
}
weightArr = new int[n];
// 初始化权重数组,初始化是每个分量下的权重都为1
for (int i = 0; i < weightArr.length; i++) {
weightArr[i] = 1;
}
}
void union(int p, int q) {
// 找到p的标识
int pId = find(p);
// 找到q的标识
int qId = find(q);
// 如果两个标识相等,代表已经合并
if (pId == qId) return;
// 将权重小的树,合并到权重大的树下
if (weightArr[pId] < weightArr[qId]) {
id[pId] = qId;
weightArr[qId] += weightArr[pId];
} else {
id[qId] = pId;
weightArr[pId] += weightArr[qId];
}
// 每次合并操作,会降低一个不同分量组
count--;
}
int find(int p) {
if (p == id[p]) return p;
// 递归直接找到根节点,将分量直接指向根节点,完成彻底的路径压缩.
id[p] = find(id[p]);
return id[p];
}
/**
* 获取以屋顶为根节点的分量总数
*
* @param p
* @return
*/
int getWeight(int p) {
int root = find(p);
return weightArr[root];
}
}
算法代码
class Solution {
private static int rowCount = 0;
private static int colCount = 0;
public static int[] hitBricks(int[][] grid, int[][] hits) {
rowCount = grid.length;
colCount = grid[0].length;
// 一 构建逆向的初始数组
// 1.1 将数据集copy一份
int[][] tenet = new int[rowCount][colCount];
for (int i = 0; i < tenet.length; i++) {
for (int j = 0; j < tenet[i].length; j++) {
tenet[i][j] = grid[i][j];
}
}
// 1.2 执行hit操作,把所有点打掉
for (int[] hit : hits) {
tenet[hit[0]][hit[1]] = 0;
}
// 二 初始化并查集
// 矩阵分量总数为 rowCount * colCount,+1代表额外预留出屋顶这个虚拟分量的位置
int size = rowCount * colCount;
HitBricksUnionFind uf = new HitBricksUnionFind(size + 1);
// 2.1 先把第一排分量和屋顶进行合并操作
for (int i = 0; i < tenet[0].length; i++) {
if (tenet[0][i] == 1) {
uf.union(getUfIndex(0, i), size);
}
}
// 2.2 从第二排开始,合并链接的分量;1)与左侧连通;2)与上方连通
for (int i = 1; i < tenet.length; i++) {
for (int j = 0; j < tenet[i].length; j++) {
if (tenet[i][j] == 1) {
// 有分量的地方才需要连通
if (tenet[i - 1][j] == 1) {
// 如果上方也有砖块,进行合并
uf.union(getUfIndex(i, j), getUfIndex(i - 1, j));
}
if (j > 0 && tenet[i][j - 1] == 1) {
// 如果左侧方也有砖块,进行合并
uf.union(getUfIndex(i, j), getUfIndex(i, j - 1));
}
}
}
}
// 三 执行粘合操作,粘合操作即为hit操作的逆向,将hits倒叙遍历
// 3.1 定义四个方向
int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int[] res = new int[hits.length];
for (int k = hits.length - 1; k >= 0; k--) {
int[] hit = hits[k];
int i = hit[0];
int j = hit[1];
// 3.2 如果原有数据集敲击位置为0,说明原本敲空,不需要粘合
if (grid[i][j] == 0) continue;
int totalCount = uf.getWeight(size);
if (i == 0) {
uf.union(j, size);
}
// 3.3 四个方向在没有越界的情况下,如果有砖块就合并
for (int[] ints : dir) {
int m = ints[0];
int n = ints[1];
int x = i + m;
int y = j + n;
if (inArea(x, y) && tenet[x][y] == 1) {
uf.union(getUfIndex(x, y), getUfIndex(i, j));
}
}
int totalCountNew = uf.getWeight(size);
// 因为题目需要排除敲击出的砖块,所以需要减1,为了防止出现负数,与0去最大值.
res[k] = Math.max(0, totalCountNew - totalCount - 1);
// 3.4 将粘合位置补上砖块
tenet[i][j] = 1;
}
return res;
}
private static int getUfIndex(int x, int y) {
return x * colCount + y;
}
private static boolean inArea(int x, int y) {
return x >= 0 && x < rowCount && y >= 0 && y < colCount;
}
}
