求索引间距至少为k的数组元素最小绝对差的高效解法

安全阿岳

2026-7-12

高效解决方案（O(n log n) 时间复杂度）

你之前认为排序不可行的误区在于担心丢失索引信息，但实际上我们可以通过维护有序集合结合索引筛选，或者绑定元素与索引后排序的方式，在O(n log n)时间内解决问题，远优于你之前的O(n²)或O(n*数值范围)解法。

方法一：遍历 + 有序集合维护（推荐）

核心思路：遍历数组时，只保留所有与当前索引间距≥k的历史元素（即索引≤当前索引 -k的元素），将这些元素存入有序集合。对于当前元素，只需在有序集合中查找最接近它的两个元素（比它大的最小值、比它小的最大值），计算绝对差即可得到候选最小差。

Python实现（使用标准库bisect维护有序列表，若允许第三方库可改用sortedcontainers.SortedList将插入时间优化至O(log n)）：

import bisect

def minimum_difference_with_k(nums, k):
    min_diff = float('inf')
    sorted_history = []  # 维护索引<=i-k的元素的有序列表
    
    for i in range(len(nums)):
        # 当当前索引i >=k时，将i-k位置的元素加入有序列表（该元素与后续元素的索引差≥k）
        if i >= k:
            bisect.insort(sorted_history, nums[i - k])
        
        # 从有序列表中找最接近当前元素的值，计算最小差
        if sorted_history:
            pos = bisect.bisect_left(sorted_history, nums[i])
            # 检查插入位置右侧的元素
            if pos < len(sorted_history):
                min_diff = min(min_diff, abs(nums[i] - sorted_history[pos]))
            # 检查插入位置左侧的元素
            if pos > 0:
                min_diff = min(min_diff, abs(nums[i] - sorted_history[pos - 1]))
    
    return min_diff if min_diff != float('inf') else 0

方法二：绑定元素与索引后排序 + 双指针

另一种思路是将每个元素与其原始索引绑定为元组，按元素值排序。由于排序后最小绝对差必然出现在相邻元素中，我们只需遍历排序后的列表，检查每对元素的索引差是否≥k，同时用滑动窗口高效筛选符合条件的元素对：

def minimum_difference_with_k(nums, k):
    # 绑定元素值与原始索引，按值排序
    sorted_pairs = sorted((num, idx) for idx, num in enumerate(nums))
    n = len(sorted_pairs)
    min_diff = float('inf')
    
    left = 0
    for right in range(1, n):
        # 缩小窗口，直到窗口内left与right的索引差≥k
        while abs(sorted_pairs[right][1] - sorted_pairs[left][1]) < k:
            left += 1
        # 计算当前窗口内的最小差（排序后相邻元素差最小）
        min_diff = min(min_diff, abs(sorted_pairs[right][0] - sorted_pairs[left][0]))
        # 额外检查left-1（如果存在），避免错过符合条件的更近元素
        if left > 0:
            min_diff = min(min_diff, abs(sorted_pairs[right][0] - sorted_pairs[left-1][0]))
    
    return min_diff if min_diff != float('inf') else 0

复杂度说明

方法一：若使用bisect.insort，插入操作最坏为O(n)，总时间复杂度O(n²)；若改用sortedcontainers.SortedList，插入和查询均为O(log n)，总时间复杂度O(n log n)，适合大数据量场景。
方法二：排序时间O(n log n)，双指针遍历O(n)，总时间复杂度O(n log n)，无需第三方库即可实现高效求解。

为什么排序是可行的？

你之前担心排序会丢失索引信息，但通过将元素与索引绑定，我们可以在排序后依然追踪原始位置，从而筛选出满足索引间距要求的元素对。排序的核心作用是将最小绝对差的候选范围从所有元素对缩小到相邻元素对，大幅减少需要比较的次数。

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