这是 LeetCode 3244. 新增道路查询后的最短距离 II困难版的 Java 实现。题目分析本题与简单版3243的区别在于数据范围扩大到 n, queries.length ≤ 10^5且关键约束新增的道路不会交叉不存在 queries[i][0] queries[j][0] queries[i][1] queries[j][1]。由于道路不交叉贪心策略成立遇到捷径就走捷径是最优的。被跳过的城市不可能再出现在最短路径中。核心思路区间并查集将问题转化为维护有效节点集合- 初始有 n 个城市最短路径长度为 n-1经过所有边- 每新增一条道路 [u, v]相当于可以跳过 (u, v) 之间的所有城市- 使用并查集维护下一个有效节点将区间 [u, v-1] 内的节点合并到 v-1 的代表元- 每次合并减少一个连通块答案就是当前连通块数量并查集数组含义fa[i] 表示从节点 i 出发下一个未被覆盖的节点带路径压缩。Java 代码javaclass UnionFind {public final int[] fa;public UnionFind(int size) {fa new int[size];// 初始化每个节点指向自己for (int i 1; i size; i) {fa[i] i;}}public int find(int x) {if (fa[x] ! x) {fa[x] find(fa[x]); // 路径压缩}return fa[x];}}class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {UnionFind uf new UnionFind(n - 1);int[] ans new int[queries.length];int cnt n - 1; // 初始连通块数量 边数 n-1for (int qi 0; qi queries.length; qi) {int l queries[qi][0]; // 起点int r queries[qi][1] - 1; // 终点前一条边int fr uf.find(r); // 找到 r 所在集合的代表元// 遍历 [l, r) 区间内的所有节点将它们合并到 frfor (int i uf.find(l); i r; i uf.find(i 1)) {uf.fa[i] fr; // 直接指向代表元cnt--; // 每合并一次连通块数减1}ans[qi] cnt;}return ans;}}代码解释关键部分 说明fa[i] 节点 i 的父节点带路径压缩find(x) 查找 x 所在集合的代表元cnt n - 1 初始最短路径经过 n-1 条边r queries[qi][1] - 1 将城市编号转换为边编号城市 i 到 i1 的边编号为 ifor (int i uf.find(l); i r; i uf.find(i 1)) 跳跃式遍历跳过已被合并的节点均摊 O(1)复杂度分析- 时间复杂度O((n q) × α(n))其中 α 是阿克曼函数的反函数近似常数。每个节点最多被合并一次。- 空间复杂度O(n)另一种思路贪心 TreeSet如果不使用并查集也可以用 TreeSet 维护剩余城市javaclass Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {TreeSetInteger set new TreeSet();for (int i 0; i n; i) {set.add(i);}int[] ans new int[queries.length];for (int i 0; i queries.length; i) {int l queries[i][0];int r queries[i][1];// 删除 (l, r) 开区间内的所有城市// 这些城市被捷径覆盖不可能出现在最短路径中Integer cur set.higher(l); // 第一个大于 l 的元素while (cur ! null cur r) {set.remove(cur);cur set.higher(l); // 继续找下一个}ans[i] set.size() - 1; // 剩余节点数 - 1 边数}return ans;}}时间复杂度O((n q) log n)在数据范围较小时也可通过但并查集版本更优。