千问 LeetCode 1632.矩阵转换后的排名 public int[][] matrixRankTransform(int[][] matrix)

这道题是 LeetCode 中难度较高的题目，考察了排序、贪心算法以及并查集的综合应用。

🧐 题目解析

核心目标是为矩阵中的每个元素分配一个“秩”（rank），秩从 1 开始，且需要满足以下规则：
1. 保序性：在同一行或同一列中，如果元素 p > valueToPositions = new TreeMap();
for (int i = 0; i new ArrayList()).add(new int[]{i, j});
}
}

// 记录每行和每列当前的最大秩
int[] rowMaxRank = new int[m];
int[] colMaxRank = new int[n];

int[][] result = new int[m][n];

// 并查集，大小为 m + n，前 m 个代表行，后 n 个代表列
UnionFind uf = new UnionFind(m + n);

// 2. 按值从小到大处理
for (List positions : valueToPositions.values()) {
// 3. 将当前值的所有位置通过并查集连接起来
// 如果一个元素在 (r, c)，就将行 r 和列 c+m 连接
for (int[] pos : positions) {
uf.union(pos[0], pos[1] + m);
}

// 用于存储每个连通分量的根节点到该分量内所有位置的映射
Map> components = new HashMap();
for (int[] pos : positions) {
int root = uf.find(pos[0]); // 行节点的根可以代表整个连通分量
components.computeIfAbsent(root, k -> new ArrayList()).add(pos);
}

// 4 & 5. 对每个连通分量计算秩并更新结果
for (List component : components.values()) {
// 找出该连通分量中所有位置对应的行和列的最大秩
int maxRank = 0;
for (int[] pos : component) {
int r = pos[0];
int c = pos[1];
maxRank = Math.max(maxRank, Math.max(rowMaxRank[r], colMaxRank[c]));
}

// 该连通分量所有元素的秩为 maxRank + 1
int finalRank = maxRank + 1;
for (int[] pos : component) {
int r = pos[0];
int c = pos[1];
result[r][c] = finalRank;
// 更新行和列的最大秩
rowMaxRank[r] = finalRank;
colMaxRank[c] = finalRank;
}
}

// 处理完当前值后，重置并查集，为下一批值做准备
for (int[] pos : positions) {
uf.reset(pos[0]);
uf.reset(pos[1] + m);
}
}

return result;
}
}