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

给你一个下标从 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

请看 视频讲解 第三题。

[sol-Python3]

from sortedcontainers import SortedList

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        ans = inf
        sl = SortedList((-inf, inf))  # 哨兵
        for v, y in zip(nums, nums[x:]):
            sl.add(v)
            j = sl.bisect_left(y)
            ans = min(ans, sl[j] - y, y - sl[j - 1])
        return ans

[sol-Java]

class Solution {
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        var a = nums.stream().mapToInt(i -> i).toArray();
        int ans = Integer.MAX_VALUE, n = a.length;
        var s = new TreeSet<Integer>();
        s.add(Integer.MAX_VALUE); // 哨兵
        s.add(Integer.MIN_VALUE / 2);
        for (int i = x; i < n; i++) {
            s.add(a[i - x]);
            int y = a[i];
            ans = Math.min(ans, Math.min(s.ceiling(y) - y, y - s.floor(y)));
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int minAbsoluteDifference(vector<int> &nums, int x) {
        int ans = INT_MAX, n = nums.size();
        set<int> s = {INT_MIN / 2, INT_MAX}; // 哨兵
        for (int i = x; i < n; i++) {
            s.insert(nums[i - x]);
            int y = nums[i];
            auto it = s.lower_bound(y); // 注意用 set 自带的 lower_bound，具体见视频中的解析
            ans = min(ans, min(*it - y, y - *prev(it))); // 注意不能写 *--it，这是未定义行为：万一先执行了 --it，前面的 *it-y 就错了
        }
        return ans;
    }
};

[sol-Go]

// import "github.com/emirpasic/gods/trees/redblacktree"
func minAbsoluteDifference(nums []int, k int) int {
	ans := math.MaxInt
	t := redblacktree.NewWithIntComparator()
	t.Put(math.MaxInt, nil) // 哨兵
	t.Put(math.MinInt/2, nil)
	for i, y := range nums[k:] {
		t.Put(nums[i], nil)
		c, _ := t.Ceiling(y)
		f, _ := t.Floor(y)
		ans = min(ans, min(c.Key.(int)-y, y-f.Key.(int)))
	}
	return ans
}

func min(a, b int) int { if b < a { return b }; return a }

复杂度分析

• 时间复杂度：\mathcal{O}((n-x)\log (n-x))，其中 n 为 nums 的长度。
• 空间复杂度：\mathcal{O}(n-x)。