目标
给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。
同时给你一个长度为 n 的整数数组 nums，该数组按 非递减 顺序排序，以及一个整数 maxDiff。
如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。
此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。
返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 ui 和 vi 之间存在路径，否则为 false。
示例 1：
输入: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]
输出: [true,false]
解释:
查询 [0,0]：节点 0 有一条到自己的显然路径。
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |1 - 3| = 2，大于 maxDiff。
因此，在处理完所有查询后，最终答案为 [true, false]。示例 2：
输入: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]
输出: [false,false,true,true]
解释:
生成的图如下：
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |2 - 5| = 3，大于 maxDiff。
查询 [0,2]：节点 0 和节点 2 之间没有边，因为 |nums[0] - nums[2]| = |2 - 6| = 4，大于 maxDiff。
查询 [1,3]：节点 1 和节点 3 之间存在路径通过节点 2，因为 |nums[1] - nums[2]| = |5 - 6| = 1 和 |nums[2] - nums[3]| = |6 - 8| = 2，都小于等于 maxDiff。
查询 [2,3]：节点 2 和节点 3 之间有一条边，因为 |nums[2] - nums[3]| = |6 - 8| = 2，等于 maxDiff。
因此，在处理完所有查询后，最终答案为 [false, false, true, true]。说明：
- 1 <= n == nums.length <= 10^5
- 0 <= nums[i] <= 10^5
- nums 按 非递减 顺序排序。
- 0 <= maxDiff <= 10^5
- 1 <= queries.length <= 10^5
- queries[i] == [ui, vi]
- 0 <= ui, vi < n
思路
有 n 个节点编号为 0 ~ n - 1，节点之间的边由非递减数组 nums 与变量 maxDiff 给出，如果两个节点的差值不超过 maxDiff 则表示它们之间有一条无向边。有一个查询数组 queries，返回每次查询的两个节点是否连通。
由于 nums 非递减，只需考虑相邻节点是否连通即可。如果相邻节点不连通，那么跨过这对节点的区间都不连通。可以使用并查集维护连通性。
代码
/**
* @date 2026-07-09 8:50
*/
public class PathExistenceQueries3532 {
class UnionFind {
private final int[] fa;
public UnionFind(int n) {
fa = new int[n];
Arrays.setAll(fa, i -> i);
}
public int find(int i) {
if (i != fa[i]) {
fa[i] = find(fa[i]);
}
return fa[i];
}
public void union(int a, int b) {
int x = find(a);
int y = find(b);
if (x < y) {
fa[y] = x;
} else if (x > y) {
fa[x] = y;
}
}
}
public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
UnionFind uf = new UnionFind(n);
for (int i = 1; i < n; i++) {
if (Math.abs(nums[i] - nums[i - 1]) <= maxDiff) {
uf.union(i, i - 1);
}
}
boolean[] res = new boolean[queries.length];
for (int i = 0; i < queries.length; i++) {
res[i] = uf.find(queries[i][0]) == uf.find(queries[i][1]);
}
return res;
}
}
性能
