题目描述
给你一个整数 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 之间的 最短距离 。如果两节点之间不存在路径，则返回 -1。
返回一个数组 answer，其中 answer[i] 是第 i 个查询的结果。
注意：节点之间的边是无权重（unweighted）的。
示例 1：
输入: n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]
输出: [1,1]
解释:
生成的图如下：
| 查询 | 最短路径 | 最短距离 |
| [0, 3] | 0 → 3 | 1 |
| [2, 4] | 2 → 4 | 1 |
因此，输出为 [1, 1]。
示例 2：
输入: n = 5, nums = [5,3,1,9,10], maxDiff = 2, queries = [[0,1],[0,2],[2,3],[4,3]]
输出: [1,2,-1,1]
解释:
生成的图如下：
| 查询 | 最短路径 | 最短距离 |
| [0, 1] | 0 → 1 | 1 |
| [0, 2] | 0 → 1 → 2 | 2 |
| [2, 3] | 无 | -1 |
| [4, 3] | 3 → 4 | 1 |
因此，输出为 [1, 2, -1, 1]。
示例 3：
输入: n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]
输出: [0,-1,-1]
解释:
由于以下原因，任意两个节点之间都不存在边：
- 节点 0 和节点 1：
|nums[0] - nums[1]| = |3 - 6| = 3 > 1 - 节点 0 和节点 2：
|nums[0] - nums[2]| = |3 - 1| = 2 > 1 - 节点 1 和节点 2：
|nums[1] - nums[2]| = |6 - 1| = 5 > 1
因此，不存在任何可以到达其他节点的节点，输出为 [0, -1, -1]。
提示：
1 <= n == nums.length <= 1050 <= nums[i] <= 1050 <= maxDiff <= 1051 <= queries.length <= 105queries[i] == [ui, vi]0 <= ui, vi < n
解法
方法一：排序 + 二分倍增
关键观察：若两个节点的值之差的绝对值不超过 maxDiff，则它们之间有边。将节点按值排序后，从值较小的节点出发，每一步贪心地跳到当前能到达的值最大的节点，即可得到最短路径。
预处理步骤如下：
- 将
(nums[i], i) 按值排序； - 使用双指针：对于排序后的每个位置
l，找到满足 pairs[r].first - pairs[l].first <= maxDiff 的最右位置 r，令 f[i][0] = j，表示从节点 i 一步跳到值差不超过 maxDiff 的、值最大的节点 j； - 通过倍增预处理
f[i][k]，表示从节点 i 跳 \(2^k\) 步后到达的节点。
查询时，设 nums[u] <= nums[v]：
- 若
u == v，答案为 \(0\)； - 若
nums[u] == nums[v]，答案为 \(1\)； - 否则用倍增求最少跳跃次数，使到达节点的值不小于
nums[v]；若仍无法到达则返回 \(-1\)，否则答案为 \(d + 1\)。
时间复杂度 \(O(n \log n + (n + q) \log n)\)，空间复杂度 \(O(n \log n)\)。其中 \(n\) 为节点数，\(q\) 为查询次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | class Solution:
def pathExistenceQueries(
self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]
) -> List[int]:
pairs = sorted((x, i) for i, x in enumerate(nums))
m = 20
f = [[0] * m for _ in range(n)]
r = n - 1
for l in range(n - 1, -1, -1):
while pairs[r][0] - pairs[l][0] > maxDiff:
r -= 1
i, j = pairs[l][1], pairs[r][1]
f[i][0] = j
for k in range(1, m):
f[i][k] = f[f[i][k - 1]][k - 1]
ans = []
for i, j in queries:
if nums[i] > nums[j]:
i, j = j, i
if i == j:
ans.append(0)
continue
if nums[i] == nums[j]:
ans.append(1)
continue
d = 0
for k in range(m - 1, -1, -1):
if nums[f[i][k]] < nums[j]:
d |= 1 << k
i = f[i][k]
if nums[f[i][0]] < nums[j]:
ans.append(-1)
else:
ans.append(d + 1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | class Solution {
public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
int[][] pairs = new int[n][2];
for (int i = 0; i < n; i++) {
pairs[i][0] = nums[i];
pairs[i][1] = i;
}
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int m = 20;
int[][] f = new int[n][m];
int r = n - 1;
for (int l = n - 1; l >= 0; l--) {
while (pairs[r][0] - pairs[l][0] > maxDiff) {
r--;
}
int i = pairs[l][1], j = pairs[r][1];
f[i][0] = j;
for (int k = 1; k < m; k++) {
f[i][k] = f[f[i][k - 1]][k - 1];
}
}
int[] ans = new int[queries.length];
for (int t = 0; t < queries.length; t++) {
int i = queries[t][0], j = queries[t][1];
if (nums[i] > nums[j]) {
int tmp = i;
i = j;
j = tmp;
}
if (i == j) {
ans[t] = 0;
continue;
}
if (nums[i] == nums[j]) {
ans[t] = 1;
continue;
}
int d = 0;
for (int k = m - 1; k >= 0; k--) {
if (nums[f[i][k]] < nums[j]) {
d |= 1 << k;
i = f[i][k];
}
}
if (nums[f[i][0]] < nums[j]) {
ans[t] = -1;
} else {
ans[t] = d + 1;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 | class Solution {
public:
vector<int> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
vector<pair<int, int>> pairs;
for (int i = 0; i < n; i++) {
pairs.emplace_back(nums[i], i);
}
sort(pairs.begin(), pairs.end());
int m = 20;
vector<vector<int>> f(n, vector<int>(m));
int r = n - 1;
for (int l = n - 1; l >= 0; l--) {
while (pairs[r].first - pairs[l].first > maxDiff) {
r--;
}
int i = pairs[l].second, j = pairs[r].second;
f[i][0] = j;
for (int k = 1; k < m; k++) {
f[i][k] = f[f[i][k - 1]][k - 1];
}
}
vector<int> ans;
for (auto& q : queries) {
int i = q[0], j = q[1];
if (nums[i] > nums[j]) {
swap(i, j);
}
if (i == j) {
ans.push_back(0);
continue;
}
if (nums[i] == nums[j]) {
ans.push_back(1);
continue;
}
int d = 0;
for (int k = m - 1; k >= 0; k--) {
if (nums[f[i][k]] < nums[j]) {
d |= 1 << k;
i = f[i][k];
}
}
if (nums[f[i][0]] < nums[j]) {
ans.push_back(-1);
} else {
ans.push_back(d + 1);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 | func pathExistenceQueries(n int, nums []int, maxDiff int, queries [][]int) []int {
pairs := make([][2]int, n)
for i, x := range nums {
pairs[i] = [2]int{x, i}
}
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
m := 20
f := make([][]int, n)
for i := range f {
f[i] = make([]int, m)
}
r := n - 1
for l := n - 1; l >= 0; l-- {
for pairs[r][0]-pairs[l][0] > maxDiff {
r--
}
i, j := pairs[l][1], pairs[r][1]
f[i][0] = j
for k := 1; k < m; k++ {
f[i][k] = f[f[i][k-1]][k-1]
}
}
ans := make([]int, 0, len(queries))
for _, q := range queries {
i, j := q[0], q[1]
if nums[i] > nums[j] {
i, j = j, i
}
if i == j {
ans = append(ans, 0)
continue
}
if nums[i] == nums[j] {
ans = append(ans, 1)
continue
}
d := 0
for k := m - 1; k >= 0; k-- {
if nums[f[i][k]] < nums[j] {
d |= 1 << k
i = f[i][k]
}
}
if nums[f[i][0]] < nums[j] {
ans = append(ans, -1)
} else {
ans = append(ans, d+1)
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 | function pathExistenceQueries(
n: number,
nums: number[],
maxDiff: number,
queries: number[][],
): number[] {
const pairs: number[][] = [];
for (let i = 0; i < n; i++) {
pairs.push([nums[i], i]);
}
pairs.sort((a, b) => a[0] - b[0]);
const m = 20;
const f = Array.from({ length: n }, () => Array(m).fill(0));
let r = n - 1;
for (let l = n - 1; l >= 0; l--) {
while (pairs[r][0] - pairs[l][0] > maxDiff) {
r--;
}
let i = pairs[l][1],
j = pairs[r][1];
f[i][0] = j;
for (let k = 1; k < m; k++) {
f[i][k] = f[f[i][k - 1]][k - 1];
}
}
const ans: number[] = [];
for (const q of queries) {
let i = q[0],
j = q[1];
if (nums[i] > nums[j]) {
[i, j] = [j, i];
}
if (i === j) {
ans.push(0);
continue;
}
if (nums[i] === nums[j]) {
ans.push(1);
continue;
}
let d = 0;
for (let k = m - 1; k >= 0; k--) {
if (nums[f[i][k]] < nums[j]) {
d |= 1 << k;
i = f[i][k];
}
}
if (nums[f[i][0]] < nums[j]) {
ans.push(-1);
} else {
ans.push(d + 1);
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 | impl Solution {
pub fn path_existence_queries(
n: i32,
nums: Vec<i32>,
max_diff: i32,
queries: Vec<Vec<i32>>,
) -> Vec<i32> {
let n = n as usize;
let mut pairs = Vec::with_capacity(n);
for (i, &x) in nums.iter().enumerate() {
pairs.push((x, i));
}
pairs.sort_unstable();
let m = 20;
let mut f = vec![vec![0; m]; n];
let mut r = n - 1;
for l in (0..n).rev() {
while pairs[r].0 - pairs[l].0 > max_diff {
r -= 1;
}
let (i, j) = (pairs[l].1, pairs[r].1);
f[i][0] = j;
for k in 1..m {
f[i][k] = f[f[i][k - 1]][k - 1];
}
}
let mut ans = Vec::with_capacity(queries.len());
for q in queries {
let (mut i, mut j) = (q[0] as usize, q[1] as usize);
if nums[i] > nums[j] {
std::mem::swap(&mut i, &mut j);
}
if i == j {
ans.push(0);
continue;
}
if nums[i] == nums[j] {
ans.push(1);
continue;
}
let mut d = 0;
for k in (0..m).rev() {
if nums[f[i][k]] < nums[j] {
d |= 1 << k;
i = f[i][k];
}
}
if nums[f[i][0]] < nums[j] {
ans.push(-1);
} else {
ans.push(d + 1);
}
}
ans
}
}
|