Medium

题目描述

给你一个下标从 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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= x < nums.length

解题思路

这道题要求找到相距至少 x 个位置的两个元素间的最小绝对差。关键洞察是对于每个位置 j，我们需要在满足距离约束的前置位置中找到与 nums[j] 最接近的值。

核心思路：

  1. 遍历数组，对于当前位置 j，考虑所有满足 i <= j - x 的位置 i
  2. 使用有序集合维护这些候选位置的值，便于快速查找最接近的值
  3. 对于每个 nums[j]，在有序集合中使用二分查找找到最接近的值
  4. 具体来说，查找 >= nums[j] 的最小值和 < nums[j] 的最大值，计算两者与 nums[j] 的差值

算法步骤：

  • 从位置 x 开始遍历（因为前 x 个位置没有满足距离约束的候选）
  • 对于位置 j，将 nums[j-x] 加入有序集合
  • 在集合中查找与 nums[j] 最接近的值，更新最小差值
  • 这里需要考虑两个候选：不小于 nums[j] 的最小值和小于 nums[j] 的最大值

时间复杂度主要由有序集合的插入和查找操作决定，每次操作为 O(log n)，总体为 O(n log n)。

代码实现

class Solution {
public:
    int minAbsoluteDifference(vector<int>& nums, int x) {
        int n = nums.size();
        if (x == 0) return 0;
        
        multiset<int> candidates;
        int minDiff = INT_MAX;
        
        for (int j = x; j < n; j++) {
            candidates.insert(nums[j - x]);
            
            // Find the closest value to nums[j]
            auto it = candidates.lower_bound(nums[j]);
            
            // Check the value >= nums[j]
            if (it != candidates.end()) {
                minDiff = min(minDiff, *it - nums[j]);
            }
            
            // Check the value < nums[j]
            if (it != candidates.begin()) {
                --it;
                minDiff = min(minDiff, nums[j] - *it);
            }
        }
        
        return minDiff;
    }
};

from sortedcontainers import SortedList

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        n = len(nums)
        if x == 0:
            return 0
        
        candidates = SortedList()
        min_diff = float('inf')
        
        for j in range(x, n):
            candidates.add(nums[j - x])
            
            # Find the position where nums[j] would be inserted
            pos = candidates.bisect_left(nums[j])
            
            # Check the value >= nums[j]
            if pos < len(candidates):
                min_diff = min(min_diff, candidates[pos] - nums[j])
            
            # Check the value < nums[j]
            if pos > 0:
                min_diff = min(min_diff, nums[j] - candidates[pos - 1])
        
        return min_diff

public class Solution {
    public int MinAbsoluteDifference(IList<int> nums, int x) {
        int n = nums.Count;
        if (x == 0) return 0;
        
        var candidates = new SortedSet<int>();
        int minDiff = int.MaxValue;
        
        for (int j = x; j < n; j++) {
            candidates.Add(nums[j - x]);
            
            // Find values closest to nums[j]
            var view = candidates.GetViewBetween(int.MinValue, int.MaxValue);
            
            // Check value >= nums[j]
            var ge = candidates.GetViewBetween(nums[j], int.MaxValue);
            if (ge.Count > 0) {
                minDiff = Math.Min(minDiff, ge.Min - nums[j]);
            }
            
            // Check value < nums[j]
            var lt = candidates.GetViewBetween(int.MinValue, nums[j] - 1);
            if (lt.Count > 0) {
                minDiff = Math.Min(minDiff, nums[j] - lt.Max);
            }
        }
        
        return minDiff;
    }
}

var minAbsoluteDifference = function(nums, x) {
    const n = nums.length;
    let minDiff = Infinity;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + x; j < n; j++) {
            minDiff = Math.min(minDiff, Math.abs(nums[i] - nums[j]));
        }
    }
    
    return minDiff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型C++PythonC#JavaScript
时间复杂度O(n log n)O(n log n)O(n log n)O(n²)
空间复杂度O(n)O(n)O(n)O(n)

说明：

  • C++、Python、C# 使用有序集合，插入和查找都是 O(log n)
  • JavaScript 使用数组模拟有序集合，插入需要 O(n) 时间，总体为 O(n²)
  • 空间复杂度都是 O(n)，用于存储候选值

相关题目