class Solution {
public:
int minAbsoluteDifference(vector<int>& nums, int x) {
}
};
7022. 限制条件下元素之间的最小绝对差
给你一个下标从 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 <= 1051 <= nums[i] <= 1090 <= x < nums.length原站题解
golang 解法, 执行用时: 228 ms, 内存消耗: 16.6 MB, 提交时间: 2023-08-14 09:42:05
// 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 }
cpp 解法, 执行用时: 272 ms, 内存消耗: 115.7 MB, 提交时间: 2023-08-14 09:41:42
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 - *--it));
}
return ans;
}
};
java 解法, 执行用时: 119 ms, 内存消耗: 63.3 MB, 提交时间: 2023-08-14 09:41:13
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;
}
}
python3 解法, 执行用时: 1116 ms, 内存消耗: 32.7 MB, 提交时间: 2023-08-14 09:40:36
# 平衡树 + 双指针
from sortedcontainers import SortedList
class Solution:
def minAbsoluteDifference(self, nums: List[int], k: int) -> int:
ans = inf
sl = SortedList([-inf, inf]) # 哨兵
for x, y in zip(nums, nums[k:]):
sl.add(x)
j = sl.bisect_left(y)
ans = min(ans, sl[j] - y, y - sl[j - 1])
return ans