写在前面

这次的周赛后两道都是图论的题目，可真是太让人头疼了，想破了头也没想出来，还是看了huanglin大佬的题解，才算是搞懂了如何求解这道题，感谢大佬。

题目

题目分析

我们不妨先从没有重复元素的矩阵开始考虑，这样可以简单许多。

无重复元素矩阵的秩

我们考虑如下例子

根据题目秩的定义，同一行或同一列中较大的元素的秩大于较小元素的秩，所以我们不妨对矩阵排序，使得较小的元素先更新秩的值，这样更新后边元素的秩时，只要考虑同行同列中最大秩的值即可，又因为题目希望秩越小越好，因此可以令当前位置的秩 = Math.max(行中最大秩，列中最大秩) + 1
比如我们更新元素9时，矩阵情况如下

这样我们就可以更新求解出无重复元素矩阵的秩了，一种朴素的思想：对矩阵排序后的每一个位置(i , j) 检查结果数组(res[i][k] 和 res[k][j])第i行、第j列是否有秩不为0的位置，若存在位置(n, m)，则更新res[i][j] = Math.max(res[i][j], res[n][m] + 1);这种方法的时间复杂度为O(n * m * (n + m))显然对于题目给出的 n, m <= 500 数据范围会超时，所以需要进行优化

优化无重复元素矩阵的秩的求法

虽然我们对于矩阵的每一个位置都检查了其所在的行和所在的列，但我们需要的值只有最大的那个秩的值，那么我们不妨每次更新位置时记录当前行、列的下标，当前位置的秩值为其所在行、列的最大值 (由于从小到大更新，后更新位置的秩必然是其所在行列的最大的秩)。
我们可以使用两个数组 int[] rowMaxRank = new int[row]; 和 int[] colMaxRank = new int[col]分别记录行和列中最大值的下标：rowMaxRank[i] = j 表示第i行目前(最后一次更新的)最大的秩是 matrix[i][j] 所对应的秩。事先可以初始化两个数组的值为 -1 ，表示任意一行、一列均没有访问过。于是我们可以得到如下伪代码更新这两个数组：

for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
        if(rowMaxRank[i] != -1){
            //当前秩为(i , rowMaxRank[i]) 对应的秩 + 1
            ...
        }
        if(colMaxRank[j] != -1){
            //当前秩为(colMaxRank[j] , j) 对应的秩 + 1
            ...
        }
        ...
        rowMaxRank[i] = j;
        colMaxRank[j] = i;
    }
}

不过你可能还会有疑问：二维矩阵要怎么排序呢？

排序

虽然二维矩阵的排序我们可能不会，但是一维的肯定会呀，所以不妨直接将二维矩阵下标转换为一维矩阵，然后使用Arrays.sort()进行排序。我们可以定义一个一维的下标数组，用来存储矩阵中值对应的下标，然后对这个一维数组根据矩阵中的值进行排序即可。代码如下

int row = matrix.length, col = matrix[0].length;
Integer[] indexs = new Integer[row * col];//转换二维下标为一维，存储下标，并按照矩阵中的值大小排序
Arrays.sort(indexs, (Integer i, Integer j) -> (matrix[i / col][i % col] - matrix[j / col][j % col]));

这里使用Integer[]是因为Arrays并没有提供int类型数组的Comparator，所以使用包装类进行排序。
这样排过序之后，最小的数据的下标为index = indexs[0];，那么其对应的矩阵中的下标也就是matrix[index / col][index % col]，这样就可以对排序后的矩阵操作了。

包含重复元素的矩阵的秩

有了上边的铺垫，就可以思考怎么处理包含重复元素的矩阵了。由于题目给出了定义：

如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：
--- 如果 p < q ，那么 rank(p) < rank(q)
--- 如果 p == q ，那么 rank(p) == rank(q)
--- 如果 p > q ，那么 rank(p) > rank(q)

重复元素的秩相等，这会带来什么影响呢？考虑下边的例子

对于图上相等的两个2，上边的2是同一行同一列中的最小元素，其值理应为1，但是跟他同一列的下边的2并不是他所在行的最小值，那么为了保证相同元素的秩相等，只能将上边的2的秩变为2。
也就是说，相同的元素秩相等，使得可能较小的秩变大了，为了保证答案的正确，我们更新相同元素的秩时，必须保证其秩为同行同列中相同元素秩的最大值
那么疑问就出现了，如何保证相同元素能一起更新为最大值呢？一起？并查集的使用也就顺理成章了，使用一个 leader 下标代表所有同行同列的相同元素(这里的同行同列包含传递性，也就是相同元素构成L形也是同行同列)，求解时，他们的秩为更新过程中的最大值即可。换句话说，我们不再是更新指定位置 (i , j) 的秩，而是更新他的 leader 的秩，并取最大值，其他方面与上述无重复元素矩阵秩的求法相同。

完整代码

综上所述，我们就可以得到完整代码了。

class Solution {

    int[] p;//并查集，用于合并相同大小的元素，保证相同大小的元素秩相同，且应为这些相同元素中秩的最大值
    int[] vals;//对应下标的秩的值(下标使用indexs数组中的下标值表示)
    Integer[] indexs;//转换二维下标为一维，存储下标，并按照矩阵中的值大小排序

    //默写并查集
    public int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    public void union(int a, int b){
        int pa = find(a), pb = find(b);
        if(pa != pb)
            p[pb] = pa;
    }

    public int[][] matrixRankTransform(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        p = new int[row * col];
        vals = new int[row * col];
        indexs = new Integer[row * col];

        //初始化indexs和并查集p
        for(int i = 0; i < row * col; i++){
            indexs[i] = i;
            p[i] = i;
        }
        
        //按照矩阵中的值排序indexs
        Arrays.sort(indexs, (Integer i, Integer j) -> (matrix[i / col][i % col] - matrix[j / col][j % col]));

        /* 由于经过排序后，小的元素先考虑，如果出现更新的位置(i, j) 所在的行、列已
           经更新过，那么当前位置的秩必然大于等于已经更新过的位置的秩，因此记录
           i行，j列之前最后一次更新秩的索引，然后根据索引找到最后一次更新的秩的值
           从行列取到最大值就是(i, j)位置的秩了。*/
        int[] rowMaxRank = new int[row];//rowMaxRank[i] = j 表示第i行目前(上一次更新的)最大的秩是 matrix[i][j] 的秩
        int[] colMaxRank = new int[col];//colMaxRank[j] = i 表示第j列目前(上一次更新的)最大的秩是 matrix[i][j] 的秩
        //初始化
        Arrays.fill(rowMaxRank, -1);
        Arrays.fill(colMaxRank, -1);

        int pos = 0;//遍历矩阵的索引
        while(pos < row * col){
            int val = 1;//每个位置的秩初始值
            int idx = indexs[pos];//获得排序后，第pos位置存储的索引

            //将索引转换回矩阵的下标
            int i = idx / col;
            int j = idx % col;

            //若i行中有更新过的位置
            if(rowMaxRank[i] != -1){
                //获取最后一次更新过的下标，以及秩的值
                int k = rowMaxRank[i];
                int tmpIdx = i * col + k;
                int tmpLeader = find(tmpIdx);
                int tmpVal = vals[tmpLeader];

                //相同元素秩相等
                if(matrix[i][j] == matrix[i][k]){
                    //合并相同元素
                    union(idx, tmpIdx);
                    val = tmpVal;
                }else{
                    //当前元素大于最后一次更新的元素，那么秩也要大于tmpVal
                    val = tmpVal + 1;
                }
            }

            //若j列中有更新过的位置
            if(colMaxRank[j] != -1){
                //获取最后一次更新过的下标，以及秩的值
                int k = colMaxRank[j];
                int tmpIdx = k * col + j;
                int tmpLeader = find(tmpIdx);
                int tmpVal = vals[tmpLeader];

                //相同元素秩相等
                if(matrix[i][j] == matrix[k][j]){
                    //合并相同元素
                    union(idx, tmpIdx);
                    //由于在rowMaxRank[i] != -1 的条件中可能更新过了val，而我们需要的是行、列中最大的秩，故取max
                    val = Math.max(val, tmpVal);
                }else{
                    //当前元素大于最后一次更新的元素，那么秩也要大于tmpVal
                    //取max理由同上
                    val = Math.max(val, tmpVal + 1);
                }
            }

            //更新最大秩的索引
            rowMaxRank[i] = j;
            colMaxRank[j] = i;

            //更新当前索引位置的秩的值，由于有相同元素，故只更新当前位置leader的秩的值
            int leader = find(idx);
            vals[leader] = val;
            pos++;
        }

        //将vals中每个元素的秩转化到二维矩阵返回
        int[][] res = new int[row][col];
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                int idx = i * col + j;
                res[i][j] = vals[find(idx)];
            }
        }
        return res;
    }
}

代码中的注释以及开篇的讲解已经很详细了，我就不在过多赘述了。
如果文章哪里有问题还请指出，感恩相遇~~