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

https://leetcode.cn/problems/minimum-absolute-difference-between-elements-with-constraint/

熟练运用二分查找


public class LeetCode02 {

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(74);
        nums.add(40);
        nums.add(99);
//        nums.add(168);
        System.out.println(minAbsoluteDifference(nums, 1));
        // 8084511998
    }


    public static int minAbsoluteDifference(List<Integer> nums, int x) {
        int min = Integer.MAX_VALUE;
        List<Integer> sortList = new ArrayList<>();
        for (int i = x; i < nums.size(); i++) {
//            addNumToSub(sortList, nums.get(i));
            addToMinSub(sortList, nums.get(i - x));
            min = Math.min(min, minSub(sortList, nums.get(i)));
            if (min == 0) {
                break;
            }
        }
        return min;
    }

    private static void addToMinSub(List<Integer> sortList, int value) {
        if (sortList.size() == 0) {
            sortList.add(value);
        } else if (sortList.get(0) >= value) {
            sortList.add(0, value);
        } else if (sortList.get(sortList.size() - 1) <= value) {
            sortList.add(value);
        } else {
            int left = 0, right = sortList.size() - 1;
            while (right - left > 1) {
                int mid = (right - left) / 2 + left;
                int num = sortList.get(mid);
                if (num == value) {
                    return;
                }
                left = num < value ? mid : left;
                right = num > value ? mid : right;
            }
            sortList.add(right, value);
        }
    }

    private static int minSub(List<Integer> sortList, int value) {
        if (sortList.get(0) >= value) {
            return sortList.get(0) - value;
        }
        if (sortList.get(sortList.size() - 1) <= value) {
            return value - sortList.get(sortList.size() - 1);
        }

        int left = 0, right = sortList.size() - 1;
        while (right - left > 1) {
            int mid = (right - left) / 2 + left;
            int num = sortList.get(mid);
            if (num == value) {
                return 0;
            }
            left = num < value ? mid : left;
            right = num > value ? mid : right;
        }
        int low = sortList.get(left);
        int high = sortList.get(right);
        return Math.min(value - low, high - value);
    }
}