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

You are given a 0-indexed integer array nums and an integer x.

Find the minimum absolute difference between two elements in the array that are at least x indices apart.

In other words, find two indices i and j such that abs(i - j) >= x and abs(nums[i] - nums[j]) is minimized.

Return an integer denoting the minimum absolute difference between two elements that are at least x indices apart.

 

Example 1:

Input: nums = [4,3,2,4], x = 2
Output: 0
Explanation: We can select nums[0] = 4 and nums[3] = 4. 
They are at least 2 indices apart, and their absolute difference is the minimum, 0. 
It can be shown that 0 is the optimal answer.

Example 2:

Input: nums = [5,3,2,10,15], x = 1
Output: 1
Explanation: We can select nums[1] = 3 and nums[2] = 2.
They are at least 1 index apart, and their absolute difference is the minimum, 1.
It can be shown that 1 is the optimal answer.

Example 3:

Input: nums = [1,2,3,4], x = 3
Output: 3
Explanation: We can select nums[0] = 1 and nums[3] = 4.
They are at least 3 indices apart, and their absolute difference is the minimum, 3.
It can be shown that 3 is the optimal answer.

 

Constraints:

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

/*
 * 思路：
 * 1. 使用IntStream遍历所有可能的下标对(i, j)，其中i从0到nums.length - x - 1，j从i + x到nums.length。
 * 2. 计算每一对(i, j)的差值绝对值，并将其收集到一个流中。
 * 3. 使用min()方法找到流中的最小值。
 */
import java.util.stream.IntStream;
public class Solution {
    public int minAbsoluteDifference(int[] nums, int x) {
        return IntStream.range(0, nums.length - x)
                        .flatMap(i -> IntStream.range(i + x, nums.length)
                                               .map(j -> Math.abs(nums[i] - nums[j])))
                        .min()
                        .orElse(Integer.MAX_VALUE);
    }
}

这道题目的基本思路是利用滑动窗口和二分查找。首先，定义一个列表 `pre` 用以存储滑动窗口中的元素（窗口大小为 `x`），并且保持这个列表有序。遍历数组 `nums` 从下标 `x` 开始，每次将下标 `i-x` 的元素插入到 `pre` 中的适当位置以保持列表的有序性。对于每个 `i`，我们使用二分查找确定 `nums[i]` 在 `pre` 中的位置，然后计算 `nums[i]` 和它前后元素的差的绝对值，以此来找出最小的差值。这个方法通过动态维护一个有序数组来快速计算任意元素与其距离至少为 `x` 的元素的最小绝对差。

O((n-x) log x)

O(x)