算法/数据结构：计算dist数组——dist[k]为数组中小于k的元素最大位置间距

首先明确需求：给定数组int[] arr，计算int[] dist，其中dist[k]表示原数组中所有小于k的元素按原顺序排列后，相邻两个元素的位置差的最大值。这里的“相邻”指的是该子序列里的连续元素，和原数组相邻、数值连续都无关。比如示例中arr=[3,8,5,6,9]，dist[6]=2——小于6的元素是[3,5]，位置分别是0和2，间距为2。

要满足时间复杂度优于O(n log n)，我们可以采用离线处理+并查集+计数排序的组合方案，下面详细拆解：

核心思路 #

1. 离线处理：不从单个k出发逐个计算，而是按元素值从小到大依次将元素加入维护结构，同步更新当前的最大间距，再把这个间距映射到对应的k区间。
2. 计数排序：用非比较类排序替代基于比较的O(n log n)排序，保证线性时间的排序效率（前提是元素取值范围可控）。
3. 并查集维护邻居：快速定位新加入元素左右最近的已加入元素，从而计算间距并更新最大值，操作近似常数时间。

具体实现步骤 #

1. 计数排序预处理元素 #

先统计每个值对应的所有元素位置，再按值从小到大遍历，得到按值排序的元素位置列表。这一步时间复杂度为O(n + range)，其中range是数组元素的取值范围，远小于n log n时就能满足要求。

2. 并查集维护已加入位置 #

并查集的作用是快速跳过已加入的位置，找到新元素左右最近的未被加入的边界：

• 初始化时每个位置的父节点是自身；
• 加入位置i后，将i的父节点更新为右侧第一个未被加入的位置，后续查找时直接跳过已加入元素。

3. 记录区间最大间距 #

每次加入元素后，计算该元素与左右邻居的间距，更新当前最大间距。所有落在(当前元素值, 下一个元素值]区间的k，对应的dist[k]就是当前的最大间距。

代码示例（Java） #

import java.util.*;

public class DistCalculator {
    public static int[] calculateDist(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int minVal = Arrays.stream(arr).min().getAsInt();
        int maxVal = Arrays.stream(arr).max().getAsInt();
        int range = maxVal - minVal + 1;

        // 计数排序桶：存储每个值对应的所有索引
        List<Integer>[] buckets = new List[range];
        for (int i = 0; i < range; i++) {
            buckets[i] = new ArrayList<>();
        }
        for (int idx = 0; idx < arr.length; idx++) {
            int val = arr[idx];
            buckets[val - minVal].add(idx);
        }

        // 生成按值从小到大排序的索引列表
        List<Integer> sortedIndices = new ArrayList<>();
        for (List<Integer> bucket : buckets) {
            sortedIndices.addAll(bucket);
        }

        int n = arr.length;
        int[] parent = new int[n + 1]; // parent[n]作为边界
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        int currentMaxGap = 0;
        Map<Integer, Integer> distMap = new HashMap<>();
        distMap.put(minVal - 1, 0); // k<=minVal时无元素，间距为0

        for (int idx : sortedIndices) {
            int right = find(parent, idx + 1);
            int left = find(parent, idx - 1);

            // 计算与左邻居的间距
            if (left != idx - 1) {
                currentMaxGap = Math.max(currentMaxGap, idx - left);
            }
            // 计算与右邻居的间距
            if (right != idx + 1) {
                currentMaxGap = Math.max(currentMaxGap, right - idx);
            }

            // 合并当前位置与右侧边界
            parent[idx] = right;
            // 记录当前值对应的最大间距
            distMap.put(arr[idx], currentMaxGap);
        }

        // 构建最终dist数组，覆盖k从1到maxVal+2的范围
        int maxK = maxVal + 2;
        int[] dist = new int[maxK];
        int lastGap = 0;
        for (int k = 1; k < maxK; k++) {
            if (distMap.containsKey(k - 1)) {
                lastGap = distMap.get(k - 1);
            }
            dist[k] = lastGap;
        }

        return dist;
    }

    private static int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]); // 路径压缩
        }
        return parent[x];
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 5, 6, 9};
        int[] dist = calculateDist(arr);
        System.out.println("dist[6] = " + dist[6]); // 输出2，符合示例预期
    }
}

时间复杂度分析 #

• 计数排序：O(n + range)，其中range是元素取值范围，只要range不超过n log n，这部分就优于O(n log n)；
• 并查集操作：路径压缩后近似O(1)，整体复杂度为O(n)；
• 最终构建dist数组：O(maxK)，可根据需求调整覆盖范围。

整体时间复杂度为O(n + range + maxK)，满足优于O(n log n)的要求。

边界情况说明 #

• 当k小于等于数组最小值时，dist[k]=0（无小于k的元素）；
• 数组只有一个元素时，所有大于该元素的k对应的dist[k]=0（无两个连续元素）；
• 存在重复元素时，计数排序会按原顺序加入，正确计算重复元素间的间距。

内容的提问来源于stack exchange，提问作者j1119