美文网首页
【算法题】2817. 限制条件下元素之间的最小绝对差

【算法题】2817. 限制条件下元素之间的最小绝对差

作者: 程序员小2 | 来源:发表于2023-08-18 10:49 被阅读0次

题目:

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

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;
    }
}


相关文章

  • 每日一题-1200. 最小绝对差

    题目 给你个整数数组 arr,其中每个元素都 不相同。 请你找到所有具有最小绝对差的元素对,并且按升序的顺序返回。...

  • 《每日一题》1200. 最小绝对差

    给你个整数数组 arr,其中每个元素都 不相同。 请你找到所有具有最小绝对差的元素对,并且按升序的顺序返回。 示例...

  • 蓝杯二十七

    /*算法训练 删除数组零元素 时间限制:1.0s 内存限制:512.0MB 提交此题 从键盘读入n个整数放入数...

  • leetcode之最小绝对差

    序 本文主要记录一下leetcode之最小绝对差 题目 题解 小结 这里先对数组进行排序,然后遍历数据判断前后差的...

  • Python 实现选择排序

    选择排序算法步骤: 找到数组中最小的那个元素中, 将它和数组的第一个元素交换位置, 在剩下的元素中找到最小的元素,...

  • 选择排序——Python

    算法步骤首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小(大)元素...

  • 排序算法02:选择排序

    算法介绍 首先,从[0,len]中找到数组中最小的元素,让它与第一个元素交换。接着从[1,len]中找出最小的元素...

  • 《算法4第二章》笔记(一)选择排序

    算法说明 首先,找到数组中最小的那个元素,其次,将它和数组中的第一个元素交换位置(如果第一个元素就是最小元素那么就...

  • Leetcode530. 二叉搜索树的最小绝对差

    题目 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例 : 解释:最小绝对差为1...

  • Kruskal算法——正确性证明

    Kruskal算法可以帮助找到最小生成树(MST). 所谓的最小生成树一种简单的理解是在给定的约束条件下, 使目标...

网友评论

      本文标题:【算法题】2817. 限制条件下元素之间的最小绝对差

      本文链接:https://www.haomeiwen.com/subject/icqdmdtx.html