3534. 图中路径存在查询 II

Hard

题目描述

给你一个整数 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 个查询的结果。

注意：节点之间的边都是无权重的。

示例 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]

示例 3：

输入：n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[1,2]]
输出：[0,-1]

提示：

1 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^5
0 <= maxDiff <= 10^5
1 <= queries.length <= 10^5
queries[i] == [ui, vi]
0 <= ui, vi < n

解题思路

这道题的核心思路是构建图并高效计算最短路径。

暴力做法：对每个查询都进行BFS，时间复杂度为 O(Q×(N+E))，其中Q是查询数，在最坏情况下会超时。

优化思路：利用稀疏表（Sparse Table）+ 二进制跳跃的思想。

排序优化：将节点按照 nums[i] 排序。排序后相邻的节点更容易满足 maxDiff 条件，这样可以更高效地构建图。
稀疏表预处理：对于每个节点，预处理它能到达的距离为 2^k 的所有节点。使用动态规划思想：
- dp[i][k] 表示从节点 i 出发，走 2^k 步能到达的所有节点
- dp[i][0] 表示从 i 直接相邻的节点
- dp[i][k] = dp[i][k-1] ∪ dp[dp[i][k-1]][k-1]
查询处理：对于每个查询 (u,v)，使用二进制分解来寻找最短路径：
- 从小到大枚举距离 d = 1,2,3,…
- 使用二进制表示，检查是否能从 u 以距离 d 到达 v
- 一旦找到，立即返回距离 d

这种方法的时间复杂度为 O(N log N + Q × N log N)，空间复杂度为 O(N^2 log N)。

实现要点：

使用邻接表存储图结构
稀疏表使用 vector<set> 存储每层可达节点
查询时进行二进制枚举距离

代码实现

class Solution {
public:
    vector<int> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        vector<pair<int, int>> sorted_nodes;
        for (int i = 0; i < n; i++) {
            sorted_nodes.push_back({nums[i], i});
        }
        sort(sorted_nodes.begin(), sorted_nodes.end());
        
        vector<vector<int>> graph(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (sorted_nodes[j].first - sorted_nodes[i].first > maxDiff) break;
                int u = sorted_nodes[i].second, v = sorted_nodes[j].second;
                graph[u].push_back(v);
                graph[v].push_back(u);
            }
        }
        
        int LOG = 17;
        vector<vector<set<int>>> dp(n, vector<set<int>>(LOG));
        
        for (int i = 0; i < n; i++) {
            for (int j : graph[i]) {
                dp[i][0].insert(j);
            }
        }
        
        for (int k = 1; k < LOG; k++) {
            for (int i = 0; i < n; i++) {
                for (int mid : dp[i][k-1]) {
                    for (int j : dp[mid][k-1]) {
                        dp[i][k].insert(j);
                    }
                }
            }
        }
        
        vector<int> result;
        for (auto& query : queries) {
            int u = query[0], v = query[1];
            if (u == v) {
                result.push_back(0);
                continue;
            }
            
            int ans = -1;
            for (int dist = 1; dist < n && ans == -1; dist++) {
                set<int> reachable;
                reachable.insert(u);
                
                for (int k = 0; k < LOG; k++) {
                    if (dist & (1 << k)) {
                        set<int> next_reachable;
                        for (int node : reachable) {
                            for (int next : dp[node][k]) {
                                next_reachable.insert(next);
                            }
                        }
                        reachable = next_reachable;
                    }
                }
                
                if (reachable.count(v)) {
                    ans = dist;
                }
            }
            result.push_back(ans);
        }
        
        return result;
    }
};

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[int]:
        sorted_nodes = sorted((nums[i], i) for i in range(n))
        
        graph = [[] for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                if sorted_nodes[j][0] - sorted_nodes[i][0] > maxDiff:
                    break
                u, v = sorted_nodes[i][1], sorted_nodes[j][1]
                graph[u].append(v)
                graph[v].append(u)
        
        LOG = 17
        dp = [[set() for _ in range(LOG)] for _ in range(n)]
        
        for i in range(n):
            for j in graph[i]:
                dp[i][0].add(j)
        
        for k in range(1, LOG):
            for i in range(n):
                for mid in dp[i][k-1]:
                    dp[i][k].update(dp[mid][k-1])
        
        result = []
        for u, v in queries:
            if u == v:
                result.append(0)
                continue
            
            ans = -1
            for dist in range(1, n):
                reachable = {u}
                
                for k in range(LOG):
                    if dist & (1 << k):
                        next_reachable = set()
                        for node in reachable:
                            next_reachable.update(dp[node][k])
                        reachable = next_reachable
                
                if v in reachable:
                    ans = dist
                    break
            
            result.append(ans)
        
        return result

public class Solution {
    public int[] PathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        var sortedNodes = nums.Select((val, idx) => new { Val = val, Idx = idx })
                              .OrderBy(x => x.Val)
                              .ToArray();
        
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (sortedNodes[j].Val - sortedNodes[i].Val > maxDiff) break;
                int u = sortedNodes[i].Idx, v = sortedNodes[j].Idx;
                graph[u].Add(v);
                graph[v].Add(u);
            }
        }
        
        int LOG = 17;
        var dp = new HashSet<int>[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashSet<int>[LOG];
            for (int j = 0; j < LOG; j++) {
                dp[i][j] = new HashSet<int>();
            }
        }
        
        for (int i = 0; i < n; i++) {
            foreach (int j in graph[i]) {
                dp[i][0].Add(j);
            }
        }
        
        for (int k = 1; k < LOG; k++) {
            for (int i = 0; i < n; i++) {
                foreach (int mid in dp[i][k-1]) {
                    foreach (int j in dp[mid][k-1]) {
                        dp[i][k].Add(j);
                    }
                }
            }
        }
        
        var result = new List<int>();
        foreach (var query in queries) {
            int u = query[0], v = query[1];
            if (u == v) {
                result.Add(0);
                continue;
            }
            
            int ans = -1;
            for (int dist = 1; dist < n && ans == -1; dist++) {
                var reachable = new HashSet<int> { u };
                
                for (int k = 0; k < LOG; k++) {
                    if ((dist & (1 << k)) != 0) {
                        var nextReachable = new HashSet<int>();
                        foreach (int node in reachable) {
                            foreach (int next in dp[node][k]) {
                                nextReachable.Add(next);
                            }
                        }
                        reachable = nextReachable;
                    }
                }
                
                if (reachable.Contains(v)) {
                    ans = dist;
                }
            }
            result.Add(ans);
        }
        
        return result.ToArray();
    }
}

var pathExistenceQueries = function(n, nums, maxDiff, queries) {
    const adj = Array.from({length: n}, () => []);
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (Math.abs(nums[i] - nums[j]) <= maxDiff) {
                adj[i].push(j);
                adj[j].push(i);
            }
        }
    }
    
    function bfs(start, end) {
        if (start === end) return 0;
        
        const queue = [start];
        const visited = new Set([start]);
        let distance = 0;
        
        while (queue.length > 0) {
            const size = queue.length;
            distance++;
            
            for (let i = 0; i < size; i++) {
                const node = queue.shift();
                
                for (const neighbor of adj[node]) {
                    if (neighbor === end) return distance;
                    if (!visited.has(neighbor)) {
                        visited.add(neighbor);
                        queue.push(neighbor);
                    }
                }
            }
        }
        
        return -1;
    }
    
    return queries.map(([u, v]) => bfs(u, v));
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	时间复杂度	空间复杂度
预处理	O(N² + N² log N)	O(N² log N)
单次查询	O(N log N)	O(N)
总体	O(N² log N + Q × N log N)	O(N² log N)

说明：

预处理阶段：构建图需要 O(N²)，构建稀疏表需要 O(N² log N)
查询阶段：每次查询最多遍历 N 个距离，每个距离的计算需要 O(N log N)
空间主要消耗在稀疏表上，存储每个节点在不同跳数下的可达节点集合

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析