相邻差分组 —— 排序数组连通分量

日期: 2026-07-09
难度: Medium
标签: 排序、连通性、分组
题目链接: 3532. 针对图的路径存在性查询 I

题目描述

有 n 个节点，每个节点 i 有权值 nums[i]（数组已排序）。若 |nums[i] - nums[j]| <= maxDiff，则 i 和 j 之间有无向边。此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。

第一次思路

暴力建图 O(n²) → 超时

第一反应是两层循环检查每一对节点，满足条件就加边，然后每次查询 BFS 判连通。建图就是 O(n²)，n 最大 1e5，不出意外的超时。

vector<vector<int>> edge(n);
for (int i = 0; i < nums.size(); i++) {
    for (int j = i + 1; j < nums.size(); j++) {
        if (abs(nums[i] - nums[j]) <= maxDiff) edge[i].push_back(j);
    }
}

二分优化建图 → 还是超时

nums 有序，想到对每个 i 二分找到最远的 j 使得 nums[j] - nums[i] <= maxDiff，然后把 [i+1, j] 全部连边。这虽然省了比较，但边数本身在最坏情况下（maxDiff 很大）仍然是 O(n²)，后面 BFS 的复杂度也扛不住。

vector<vector<int>> edge(n);
// 由于nums是有序的所以可以使用二分查找最远的点
for (int i = 0; i < nums.size(); i++) {
    int left = i, right = nums.size() - 1;
    while (left < right) {
        // 二分查找最大值记得加一防止死循环
        int mid = (left + right + 1) / 2;
        if (nums[mid] - nums[i] <= maxDiff) left = mid;
        else right = mid - 1;
    }
    // 满足条件的点是从[i + 1, left]
    for (int j = i + 1; j <= left; j++) {
        edge[i].push_back(j);
        edge[j].push_back(i);
    }
}

真正的问题是：当 maxDiff 足够大时，几乎所有点都连通，边数是 O(n²)，建图和 BFS 都无法承受。

最终方案

关键洞察：数组已经排序，连通性完全由相邻元素决定。

为什么？假设 i < k < j，如果 nums[j] - nums[i] <= maxDiff，那么一定有：

nums[k] - nums[i] <= nums[j] - nums[i] <= maxDiff

这意味着如果 i 能连到 j，i 也一定能连到中间的所有点。换句话说，连通分量在排序后的数组里一定是连续的一段。

于是问题退化为：从 nums[0] 开始扫描，相邻差 <= maxDiff 的归为一组，> maxDiff 的开启新组。查询时只需判断 u 和 v 是否属于同一组。

算法流程

vector<int> group(n, 0);
int groupNum = 0;
for (int i = 1; i < n; i++) {
    if (nums[i] - nums[i - 1] <= maxDiff) {
        group[i] = groupNum;       // 并入当前组
    } else {
        group[i] = ++groupNum;     // 开启新组
    }
}
// 查询: i 和 j 连通 ⇔ group[i] == group[j]

不需要建图，不需要 BFS/并查集，一次线性扫描 + 每次查询 O(1)。

完整代码

class Solution {
public:
    vector<bool> pathExistenceQueries(int n, vector<int>& nums,
                                       int maxDiff,
                                       vector<vector<int>>& queries) {
        vector<int> group(n, 0);
        int groupNum = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i - 1] <= maxDiff) {
                group[i] = groupNum;
            } else {
                group[i] = ++groupNum;
            }
        }
        vector<bool> ans;
        for (auto& q : queries) {
            ans.push_back(group[q[0]] == group[q[1]]);
        }
        return ans;
    }
};

复杂度分析

复杂度	分析
时间复杂度	O(n + q)，一次线性扫描分组 + 每个查询 O(1) 判断
空间复杂度	O(n)，group 数组

心得总结

排序数组的连通性判断，中间元素天然比远端元素更近——不需要检查所有点对，相邻差决定一切
当建图本身就 O(n²) 时，说明思路走错了——不是优化建图，是根本不需要建图
“连通分量是连续的一段”这个性质在很多排序区间类题目中都适用（合并区间、区间分组），关键是意识到排序后相邻约束是最强的