求解数组区间内两元素的最小绝对差查询问题

问题解决思路 #

首先明确问题：给定1索引的数组与多个[L, R]格式的查询，需要找出每个查询区间内任意两个元素的最小绝对差。比如你提到的例子：数组[2, 1, 8, 5, 11]，查询1-3对应的子数组是[2,1,8]，排序后相邻元素差为1和7，最小差是1；查询2-4对应的子数组[1,8,5]排序后是[1,5,8]，相邻差为4和3，最小差是3。

1. 单个查询的暴力解法（简单直接）

如果只处理少量查询，暴力法完全够用，思路清晰易实现：

• 步骤：
  1. 提取查询区间[L, R]对应的子数组（注意数组是1索引，代码中需转换为0索引切片）；
  2. 对子数组排序；
  3. 遍历排序后的数组，计算相邻元素的绝对差，记录最小值。

Python代码示例：

def single_query_min_diff(arr, L, R):
    # 转换为0索引切片提取子数组
    sub_array = arr[L-1:R]
    sub_array.sort()
    min_diff = float('inf')
    for i in range(1, len(sub_array)):
        current_diff = sub_array[i] - sub_array[i-1]
        if current_diff < min_diff:
            min_diff = current_diff
    return min_diff

# 测试示例
arr = [2, 1, 8, 5, 11]
print(single_query_min_diff(arr, 1, 3))  # 输出 1
print(single_query_min_diff(arr, 2, 4))  # 输出 3

这种方法的时间复杂度为O(k logk)，其中k = R-L+1是子数组长度，适合单个或少量查询场景。

2. 多查询的优化解法（应对大量查询）

如果要处理成百上千个查询，暴力法的重复排序开销会导致效率低下，这里推荐线段树维护排序区间的方法，能有效分摊排序成本：

线段树维护排序区间思路

线段树的每个节点存储对应区间的排序后数组，查询时通过合并多个区间的有序数组，快速找到最小相邻差：

• 构建线段树：
  • 叶子节点：对应数组的单个元素，存储为[arr[i]]；
  • 内部节点：将左右子节点的排序数组合并为新的排序数组；
• 查询过程：
  • 将查询区间[L, R]分解为线段树中的若干节点；
  • 合并这些节点的排序数组（或直接遍历计算最小差，无需完全合并）；
  • 遍历得到最小绝对差。

Python简化实现示例：

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [[] for _ in range(2 * self.size)]
        # 填充叶子节点
        for i in range(self.n):
            self.tree[self.size + i] = [data[i]]
        # 构建上层节点
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = sorted(self.tree[2*i] + self.tree[2*i+1])
    
    def query(self, l, r):
        # l和r为0索引的闭区间
        res = []
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                res += self.tree[l]
                l += 1
            if r % 2 == 0:
                res += self.tree[r]
                r -= 1
            l >>= 1
            r >>= 1
        res.sort()
        min_diff = float('inf')
        for i in range(1, len(res)):
            min_diff = min(min_diff, res[i] - res[i-1])
        return min_diff

# 测试
arr = [2, 1, 8, 5, 11]
st = SegmentTree(arr)
# 查询1-3（转换为0索引是0-2）
print(st.query(0, 2))  # 输出1
# 查询2-4（0索引是1-3）
print(st.query(1, 3))  # 输出3

这种方法的构建时间为O(n logn)，每个查询的时间为O(k + logn)（k为查询区间长度）。如果进一步优化，在合并有序数组时直接计算最小差而不合并完整数组，查询时间可降至O((logn)^2)，更适合大规模查询场景。

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