# 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`。这意味着在最坏的情况下数组中的元素值可能非常大，从而导致内层循环的迭代次数也将会巨大，最后可能会出现执行超时的问题。

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

```python
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:

```python
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)，大大提高了算法的执行效率。