2817. 限制条件下元素之间的最小绝对差

题目地址(2817. 限制条件下元素之间的最小绝对差)

https://leetcode.cn/problems/minimum-absolute-difference-between-elements-with-constraint

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 x 。

请你找到数组中下标距离至少为 x 的两个元素的 差值绝对值 的 最小值 。

换言之，请你找到两个下标 i 和 j ，满足 abs(i - j) >= x 且 abs(nums[i] - nums[j]) 的值最小。

请你返回一个整数，表示下标距离至少为 x 的两个元素之间的差值绝对值的 最小值 。

 

示例 1：

输入：nums = [4,3,2,4], x = 2
输出：0
解释：我们选择 nums[0] = 4 和 nums[3] = 4 。
它们下标距离满足至少为 2 ，差值绝对值为最小值 0 。
0 是最优解。
示例 2：

输入：nums = [5,3,2,10,15], x = 1
输出：1
解释：我们选择 nums[1] = 3 和 nums[2] = 2 。
它们下标距离满足至少为 1 ，差值绝对值为最小值 1 。
1 是最优解。
示例 3：

输入：nums = [1,2,3,4], x = 3
输出：3
解释：我们选择 nums[0] = 1 和 nums[3] = 4 。
它们下标距离满足至少为 3 ，差值绝对值为最小值 3 。
3 是最优解。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= x < nums.length

前置知识

• 二分查找

思路

初始思考与暴力解法

在这个题目里，我首先考虑到的是最简单的方式，也就是暴力破解的方式。这种方法的时间复杂度为O(n^2)，但是在题目的提示中还给出了数据范围为1 <= nums[i] <= 10^9。这意味着在最坏的情况下数组中的元素值可能非常大，从而导致内层循环的迭代次数也将会巨大，最后可能会出现执行超时的问题。

下面是尝试暴力解法的代码：

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        n = len(nums)
        minDiff = float('inf')

        for i in range(n):
            for j in range(i + x, n):
                absDiff = abs(nums[i] - nums[j])
                if absDiff < minDiff:
                    minDiff = absDiff

        return minDiff

寻求更高效的解决方案

在面对大规模数据或数据范围较大的情况下，我们需要寻找更高效的算法来解决这个题目，以避免超时的问题。为了降低复杂度，我们可以通过维护一个有序集合，并使用二分查找的方式进行更快的插入和查找操作，从而减少迭代次数。

在这个问题中，我们使用二分查找的思路进行优化主要有两个目的：

1. 快速插入：由于我们需要维护一个有序数组，每次插入一个新元素时，如果使用普通的插入方式，可能需要遍历整个数组才能找到插入位置，时间复杂度为O(n)。但是，如果使用二分查找，我们可以在对数时间内找到插入位置，时间复杂度为O(log n)。

2. 快速查找：对于每个索引为 i + x 的元素，我们需要在有序数组中找出最接近它的元素。如果使用普通的查找方式，可能需要遍历整个数组才能找到该元素，时间复杂度为O(n)。但是，如果使用二分查找，我们可以在对数时间内找到该元素，时间复杂度为O(log n)。

这种优化策略可以将算法的复杂度从O(n^2)降为O(N log N)。

优化策略的具体实现

1. 初始化：定义一个变量 res 为无穷大，用于存储最小的绝对差。同时定义一个 SortedList 对象 ls ，用于存储遍历过的元素并保持其有序性。

2. 遍历数组：使用 for 循环遍历 nums 数组。

3. 每次循环中，先获取当前元素 nums[i]，然后将其添加到有序列表 ls 中。

4. 获取 nums[i + x]，然后使用 SortedList.bisect_right 方法在有序列表 ls 中找到最后一个不大于 nums[i+x] 的元素的位置 idx。

5. 使用 nums[i + x] 和 ls[idx - 1]（即 nums[i + x] 在 ls 中的前一个元素）的差值更新结果 res，res 的值为当前 res 和新的差值中的较小值。

6. 如果 idx 小于 ls 的长度（即 nums[i + x] 在 ls 中的后一个元素存在），则尝试使用 nums[i + x] 和 ls[idx] 的差值更新结果 res。

7. 循环结束后，返回结果 res，这是数组中所有相隔 x 的元素的最小绝对差。

代码

• 语言支持：Python3

Python3 Code:

from sortedcontainers import SortedList

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        n = len(nums)

        # 初始化答案为无穷大
        res = float('inf')  

        # 维护前面元素的有序序列
        ls = SortedList()  

        for i in range(n - x):

            # 将nums[i]加入有序序列ls，SortedList保证插入后仍然有序
            v = nums[i]
            ls.add(v) 

            # 使用二分查找寻找前面序列中最后一个<=nums[i+x]的元素
            v = nums[i + x]
            idx = ls.bisect_right(v)

            # 使用和nums[i+x]最接近的元素更新答案,将答案更新为当前答案和新差值中的较小值
            res = min(res, abs(v - ls[idx - 1]))

            # 如果存在更接近的元素，也尝试更新答案
            if idx < len(ls):  
                res = min(res, abs(ls[idx] - v))

        return res

复杂度分析

令 n 为数组长度

• 时间复杂度：$O(nlogn)$

• 空间复杂度：$O(n)$

我们的主要循环是 for i in range(n - x)，这个循环会执行大约 n 次。在这个循环中，有两个关键操作会影响时间复杂度： ls.add(v) 和 ls.bisect_right(v)。

ls.add(v) 是一个向 SortedList 添加元素的操作，其时间复杂度为 O(log n)。ls.bisect_right(v) 是二分查找，其时间复杂度也为 O(log n)。

因此，整个循环的时间复杂度为 O(n) * O(log n) = O(n log n)。这样，我们成功地将原本暴力破解中 O(n^2) 的复杂度优化为了 O(n log n)，大大提高了算法的执行效率。