岛屿数量 II

/*
题目思路:
1. 使用Java Stream API来简化代码结构，但核心逻辑依然是使用并查集进行处理。
2. 使用数组记录每个位置的父节点，以此构建并查集。
3. 每次添加新的陆地时，利用Stream对周围的陆地进行合并操作。
4. 返回每次添加操作后的岛屿数量。
*/
 
import java.util.*;
import java.util.stream.IntStream;
 
public class NumberOfIslandsIIStream {
    private int[] parent;
    private int[] rank;
    private int count;
 
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList<>();
        parent = new int[m * n];
        rank = new int[m * n];
        Arrays.fill(parent, -1);
        count = 0;
 
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
        for (int[] position : positions) {
            int row = position[0];
            int col = position[1];
            int index = row * n + col;
            if (parent[index] != -1) { // already land
                result.add(count);
                continue;
            }
 
            parent[index] = index;
            count++;
 
            IntStream.range(0, directions.length)
                     .mapToObj(i -> new int[]{row + directions[i][0], col + directions[i][1], (row + directions[i][0]) * n + (col + directions[i][1])})
                     .filter(newPos -> newPos[0] >= 0 && newPos[0] < m && newPos[1] >= 0 && newPos[1] < n && parent[newPos[2]] != -1)
                     .forEach(newPos -> union(index, newPos[2]));
 
            result.add(count);
        }
 
        return result;
    }
 
    private int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]); // path compression
        }
        return parent[i];
    }
 
    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }
}