题解 | #数组中的最长连续子序列（java并查集）#

import java.util.*;


public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // disjoint set
        DisjointSet dSet = new DisjointSet(arr);

        for (Integer node : dSet.nodes) {
            dSet.union(node, node - 1); // 不断地寻找有无连续的节点
        }

        return dSet.maxSize;
    }
}

class DisjointSet {

    HashSet<Integer> nodes = new HashSet<>(); // 记录所有的节点
    HashMap<Integer, Integer> parent = new HashMap<>(); // 记录所有节点的直接父节点
    HashMap<Integer, Integer> size = new HashMap<>(); // 记录所有以某个节点为根的树的大小
    int maxSize = 1;

    public DisjointSet(int[] arr) {
        // 按照并查集的特性，一开始所有节点的父节点指针都指向自己（这里使用HashMap来模拟两个节点之间的指向关系）
        for (int i = 0; i < arr.length; i++) {
            parent.put(arr[i], arr[i]);
            size.put(arr[i], 1); // 初始大小为1
            nodes.add(arr[i]);
        }
    }

    public void union(int node1, int node2) {

        if (!nodes.contains(node2)) { // 有了这一步让我想了想 还不如直接用现成的集合做，因为这一步导致并没有快多少，这个代码主要写来理解一下并查集这个数据结构吧
            return;
        }

        int root1 = find(node1); //寻找父节点
        int root2 = find(node2);

        //合并两个树，大树的根作为小树根的父节点以实现合并 
        if (size.get(root1) > size.get(root2)) {
            parent.put(root2, root1);
            size.put(root1, size.get(root1) + size.get(root2));
            maxSize = Math.max(maxSize, size.get(root1));
        } else {
            parent.put(root1, root2);
            size.put(root2, size.get(root1) + size.get(root2));
            maxSize = Math.max(maxSize, size.get(root2));
        }
    }

    // 寻找树的根节点
    public int find(int node) {
        while(parent.get(node) != node) {
            int temp = parent.get(node);
            node = temp;
        }

        return node;
    } 
}