查询差绝对值的最小值

难度: Medium

一个数组 a 的 差绝对值的最小值 定义为：0 <= i < j < a.length 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值。如果 a 中所有元素都相同，那么差绝对值的最小值为 -1 。

比方说，数组 [5,2,3,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0 ，因为 a[i] 和 a[j] 必须不相等。

给你一个整数数组 nums 和查询数组 queries ，其中 queries[i] = [l_i, r_i] 。对于每个查询 i ，计算 子数组 nums[l_i...r_i] 中 差绝对值的最小值 ，子数组 nums[l_i...r_i] 包含 nums 数组（下标从 0 开始）中下标在 l_i 和 r_i 之间的所有元素（包含 l_i 和 r_i 在内）。

请你返回 ans 数组，其中 ans[i] 是第 i 个查询的答案。

子数组 是一个数组中连续的一段元素。

|x| 的值定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。

示例 1：

输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
输出：[2,1,4,1]
解释：查询结果如下：
- queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
- queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
- queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
- queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。

示例 2：

输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
输出：[-1,1,1,3]
解释：查询结果如下：
- queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。
- queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。
- queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。
- queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。

提示：

2 <= nums.length <= 10⁵
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10⁴
0 <= l_i < r_i < nums.length

Submission

运行时间: 1470 ms

内存: 26.6 MB

class Solution:
    # # 二分
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # 二分位置（2456 ms，24.3 MB）
        # 先从小到大记录数字i（1<=i<=100)出现在nums中的所有位置（实际处理时可只处理出现过的数字）
        idx = defaultdict(list)
        for i, j in enumerate(nums):  # 遍历nums，记录每个数字的索引
            idx[j].append(i)

        keys = list(sorted(idx.keys()))  # 获取排序后的键值列表
        res = []  # 初始化结果列表
        for l, r in queries:  # 遍历查询
            t = 100  # 初始化t为100
            pre = 0  # 初始化pre为0
            for i in keys:  # 遍历键值
                # 判断数字i（1<=i<=100)是否出现在此区间
                j = bisect_left(idx[i], l)  # 在idx[i]中找到l的插入位置
                if j < len(idx[i]) and idx[i][j] <= r:  # 如果插入位置的元素在查询范围内
                    # 枚举从小到大相邻两个数的差绝对值，找出最小的
                    if pre > 0 and i - pre < t:
                        t = i - pre

                    pre = i  # 更新pre为当前的i

            res.append(-1 if t == 100 else t)  # 如果t还是100，说明没有找到满足条件的数字，返回-1，否则返回t

        return res  # 返回结果列表



    # 前缀和
    # https://leetcode.cn/problems/minimum-absolute-difference-queries/solution/er-fen-wei-zhi-qu-jian-shun-xu-cha-xun-1-3zhp/
    def minDifference2(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        #前缀和（4524 ms，218.7 MB）
        s = [Counter()]
        for i in nums :
            s.append(s[-1].copy())
            s[-1][i] += 1

        res = []
        for l, r in queries :
            t = s[r+1] - s[l]
            keys = list(t.keys())
            if len(keys) == 1 :
                res.append(-1)
            else :
                keys.sort()
                res.append(min(keys[i]-keys[i-1] for i in range(1, len(keys))))

        return res

Explain

这个题解提供了两种方法来解决问题：方法一：二分查找 1. 先用一个字典 idx 记录每个数字出现在 nums 中的所有位置 2. 对于每个查询 [l, r]，遍历有序的数字键值，对每个数字 i： - 用二分查找判断 i 是否出现在区间 [l, r] 内 - 如果出现，更新相邻两数之差的最小值 t 3. 如果 t 没有被更新过，说明区间内所有数字相同，返回 -1，否则返回 t 方法二：前缀和 1. 用一个列表 s 记录到每个位置为止，每个数字出现的次数（前缀和） 2. 对于每个查询 [l, r]，用 s[r+1] - s[l] 得到区间内每个数字的出现次数 3. 如果区间内只有一个不同的数字，返回 -1，否则计算并返回有序数字间的最小差值

时间复杂度: 方法一：O(n + m * log n) 方法二：O(n + m)

空间复杂度: 方法一：O(n) 方法二：O(n)

class Solution:
    # 二分
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # 先记录每个数字出现在nums中的所有位置
        idx = defaultdict(list)
        for i, j in enumerate(nums):  
            idx[j].append(i)

        keys = list(sorted(idx.keys()))  # 获取有序的数字键值
        res = []  
        for l, r in queries:  
            t = 100  
            pre = 0  
            for i in keys:  
                # 二分查找判断数字i是否出现在区间[l, r]内
                j = bisect_left(idx[i], l)  
                if j < len(idx[i]) and idx[i][j] <= r:  
                    # 更新相邻两数之差的最小值t
                    if pre > 0 and i - pre < t:
                        t = i - pre

                    pre = i  

            # 如果t没有被更新过，说明区间内所有数字相同，返回-1，否则返回t
            res.append(-1 if t == 100 else t)  

        return res

    # 前缀和
    def minDifference2(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # 记录到每个位置为止，每个数字出现的次数（前缀和）
        s = [Counter()] 
        for i in nums:
            s.append(s[-1].copy())
            s[-1][i] += 1

        res = []
        for l, r in queries:
            # 计算区间内每个数字的出现次数  
            t = s[r+1] - s[l]  
            keys = list(t.keys())
            if len(keys) == 1:
                res.append(-1)
            else:
                keys.sort()
                # 计算有序数字间的最小差值
                res.append(min(keys[i]-keys[i-1] for i in range(1, len(keys))))

        return res

Explore

在方法一中使用二分查找，是因为每个数字在数组`nums`中的出现位置已经被储存在一个有序列表中（通过`idx`字典）。当我们需要判断一个数字是否在某个区间[l, r]内出现时，可以通过二分查找快速定位到这个范围内的第一个可能的位置，然后检查这个位置是否在给定的区间内。这比遍历整个区间来查找数字的效率要高，因为二分查找的时间复杂度是O(log n)，而直接遍历区间的复杂度可能达到O(n)，特别是当区间很大时。因此，使用二分查找可以显著提升查询效率。

在方法二中，通过构建一个前缀和数组`s`，每个元素是一个计数器（Counter），记录从数组开始到当前位置所有数字的出现次数。要计算某个区间[l, r]内各数字的出现次数，可以利用前缀和的性质：`s[r+1] - s[l]`。这里`s[r+1]`代表从数组开始到位置r的所有数字出现次数，`s[l]`代表从数组开始到位置l之前的所有数字出现次数。两者相减得到的结果便是区间[l, r]内每个数字的精确出现次数。这种方法避免了对区间内每个元素的直接统计，能够在常数时间内完成计数，提高了效率。

在方法二中返回-1的设计是为了处理特殊情况，即当查询的区间内只存在一种数字时。由题目要求是计算不同数字之间的最小差值，如果区间内只有一种数字，就不存在任何差值。因此，按照题目的逻辑，这种情况下应当返回-1，表示无法计算出有意义的差值。这样的处理符合题目求解差值的目的，也使得函数的返回结果具有明确的意义。