Medium

题目描述

给你一个整数 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

解题思路

这道题要求判断图中两个节点是否连通。由于数组 nums 已经有序，我们可以利用这个特性来高效解决问题。

思路分析

关键观察： 由于 nums 数组是有序的，如果节点 i 和 j 连通，那么它们之间的所有节点也必须连通。这意味着连通分量在有序数组中是连续的区间段。

解法 1：并查集（Union-Find）

  1. 遍历相邻节点，如果 nums[i+1] - nums[i] <= maxDiff，则连接这两个节点
  2. 对于每个查询，检查两个节点是否在同一连通分量中

解法 2：区间合并（推荐）

  1. 将连续的可连通节点合并为区间
  2. 对于每个查询，检查两个节点是否在同一区间中

由于数组有序的特性，区间合并方法更直观且效率更高。我们只需要从左到右扫描一遍，将差值不超过 maxDiff 的相邻节点归为同一连通分量。

具体步骤：

  1. 初始化第一个连通分量的起始位置
  2. 遍历数组，当发现相邻元素差值超过 maxDiff 时，结束当前连通分量
  3. 记录每个节点所属的连通分量编号
  4. 对于查询，检查两个节点的连通分量编号是否相同

代码实现

class Solution {
public:
    vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        vector<int> component(n);
        int compId = 0;
        component[0] = compId;
        
        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i-1] > maxDiff) {
                compId++;
            }
            component[i] = compId;
        }
        
        vector<bool> result;
        for (const auto& query : queries) {
            result.push_back(component[query[0]] == component[query[1]]);
        }
        
        return result;
    }
};

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        component = [0] * n
        comp_id = 0
        component[0] = comp_id
        
        for i in range(1, n):
            if nums[i] - nums[i-1] > maxDiff:
                comp_id += 1
            component[i] = comp_id
        
        result = []
        for u, v in queries:
            result.append(component[u] == component[v])
        
        return result

public class Solution {
    public bool[] PathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        int[] component = new int[n];
        int compId = 0;
        component[0] = compId;
        
        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i-1] > maxDiff) {
                compId++;
            }
            component[i] = compId;
        }
        
        bool[] result = new bool[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            result[i] = component[queries[i][0]] == component[queries[i][1]];
        }
        
        return result;
    }
}

var pathExistenceQueries = function(n, nums, maxDiff, queries) {
    const component = new Array(n);
    let compId = 0;
    component[0] = compId;
    
    for (let i = 1; i < n; i++) {
        if (nums[i] - nums[i-1] > maxDiff) {
            compId++;
        }
        component[i] = compId;
    }
    
    const result = [];
    for (const [u, v] of queries) {
        result.push(component[u]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度区间合并法并查集法
时间复杂度O(n + q)O(n α(n) + q α(n))
空间复杂度O(n)O(n)

其中 n 是节点数，q 是查询数，α(n) 是阿克曼函数的反函数。区间合并法利用了数组有序的特性，时间复杂度更优。