首页算法

2616. 最小化数对的最大差值

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。

示例 1：

输入：nums = [10,1,2,7,1,3], p = 2

输出：1

解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。

最大差值为 max (|nums [1] - nums [4]|, |nums [2] - nums [5]|) = max (0, 1) = 1 。所以我们返回 1 。

示例 2：

输入：nums = [4,2,1,2], p = 1

输出：0

解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= p <= (nums.length)/2

# 二分 + 动态规划（打家劫舍）

灵神题解

参考 https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/solution/er-fen-da-an-tan-xin-by-endlesscheng-dlxv/

二分数对中的最大差值 XX，对于检验 XX，即计算是否至少有 p 个数对，满足最大差值为 X

  • 转化为，最多有多少个数对满足最大差值为 XX，若该数对 >=p>= p，XX 通过了检验

由于下标更答案没有关系，可以直接排序，

若当前最大差值 midmid 所组成的对数 大于 pp 对

  • 往左边走，因为要寻找最大差值的最小值

若当前最大差值 mid 所组成的对数 小于 pp 对

  • 往右边走，因为不满足条件，当前最大差值 midmid 小了

求当前最大差值 mid 所组成的最多对数

dp[i+1]dp[i+1] 指的是 0∼i0 \sim i 下标元素组成的子数组最多能组成多少对相邻元素差 <=mid<=mid

例如：[1,1,2,3,7,10][1, 1, 2, 3, 7, 10]

diff：[0,1,1,4,3]diff：[0, 1, 1, 4, 3]

  • 从 diffdiff 中选择满足 diff [i] <= mid 的最多的对数，且相邻的不能选择，转换为打家劫舍

若选择 diff[i] (nums[i],nums[i−1]),dp[i]=dp[i−2]+1diff[i]\,(nums[i], nums[i - 1]),dp[i] = dp[i - 2] + 1

  • 上一个差值 diff[i−1]diff[i - 1] 不能选择

若不选择 diff[i],dp[i]=dp[i−1]diff[i],dp[i] = dp[i - 1]

参考代码

class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int min = nums[0];
        int max = nums[0];
        int n = nums.length;
        // 差值数组
        int[] diff = new int[n - 1];
        for (int i = 1; i < n; i++) {
            diff[i - 1] = nums[i] - nums[i - 1];
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int l = 0;
        // 最大差值的最大值为 max - min
        int r = max - min;
        while (l < r) {
            // 当前最大差值
            int mid = (l + r) / 2;
            // 当前最大差值所组成的最大数对数小于 p，不满足条件
            if (check(diff, mid) < p) {
                l = mid + 1;
            } else {
                // 寻找满足 >= p 的最小差值
                r = mid;
            }
        }
        return l;
    }
    private int check(int[] diff, int mxDiff) {
        int n = diff.length;
        //dp [i] : 前 i 个元素所组成的满足 diff <= mxDiff 最大数对数
        int[] dp = new int[n + 1];
        // 初始化第 1 个元素对数
        dp[1] = diff[0] <= mxDiff ? 1 : 0;
        for (int i = 2; i <= n; i++) {
            // 满足条件
            if (diff[i - 1] <= mxDiff) {
                // 选择当前元素，上一个元素不能选择，i - 2 的最大对数
                // 当前元素不选，上一个的最大对数
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + 1);
            } else {
                // 不满足，就是上一个的最大对数
                dp[i] = dp[i - 1];
            }
        }
        return dp[n];
    }
}
不使用差值数组


class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int min = nums[0];
        int max = nums[0];
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int l = 0;
        // 最大差值的最大值为 max - min
        int r = max - min;
        while (l < r) {
            // 当前最大差值
            int mid = (l + r) / 2;
            // 当前最大差值所组成的最大数对数小于 p，不满足条件
            if (check(nums, mid) < p) {
                l = mid + 1;
            } else {
                // 寻找满足 >= p 的最小差值
                r = mid;
            }
        }
        return l;
    }
    private int check(int[] nums, int mxDiff) {
        int n = nums.length;
        //dp [i] : 前 i 个元素所组成的满足 diff <= mxDiff 最大数对数
        int[] dp = new int[n];
        // 初始化第 1 个元素对数
        dp[1] = nums[1] - nums[0] <= mxDiff ? 1 : 0;
        for (int i = 2; i < n; i++) {
            // 满足条件
            if (nums[i] - nums[i - 1] <= mxDiff) {
                // 选择当前元素，上一个元素不能选择，i - 2 的最大对数
                // 当前元素不选，上一个的最大对数
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + 1);
            } else {
                // 不满足，就是上一个的最大对数
                dp[i] = dp[i - 1];
            }
        }
        return dp[n - 1];
    }
}
# 二分 + 贪心


贪心主要针对于检查二分最大差值 XX，即计算是否至少有 p 个数对，满足最大差值为 X


    

  • 转化为，最多有多少个数对满足最大差值为 XX，若该数对 >=p>= p，XX 通过了检验
    • 





img




参考代码


class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int min = nums[0];
        int max = nums[0];
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int l = 0;
        // 最大差值的最大值为 max - min
        int r = max - min;
        while (l < r) {
            // 当前最大差值
            int mid = (l + r) / 2;
            // 当前最大差值所组成的最大数对数小于 p，不满足条件
            if (check(nums, mid) < p) {
                l = mid + 1;
            } else {
                // 寻找满足 >= p 的最小差值
                r = mid;
            }
        }
        return l;
    }
    private int check(int[] nums, int mxDiff) {
        int n = nums.length;
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i - 1] <= mxDiff) {
                cnt++;
                i++;
            }
        }
        return cnt;
    }
}