点击获取AI摘要

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

给你一个下标从 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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= p <= (nums.length)/2

问题分析

给定长度为 $n$ 的整数数组 $\text{nums}$ 和整数 $p$ ，需要从中选出 $p$ 对不重叠下标，使得这 $p$ 对中差值的最大值最小。

差值定义：对一对下标 $(i,j)$ ，差值为 $\lvert \text{nums}[i] - \text{nums}[j]\rvert$ 。
每个下标最多只能出现一次。

关键在于：若假设“最大差值”上限为 $D$ ，能否在所有相邻差值 $\le D$ 的情况下选出至少 $p$ 对？
若可行，则可通过二分搜索最小的 $D$ 。

算法思路

排序
将 $\text{nums}$ 排序为 $A$ ，令 $A[0]\le A[1]\le\cdots\le A[n-1]$ 。

定义可行性检查
对给定阈值 $D$ ，我们从左到右贪心配对相邻元素：

cnt = 0, i = 0
while i < n-1 and cnt < p:
    if A[i+1] - A[i] ≤ D:
        cnt += 1
        i += 2   # 已用 i 和 i+1
    else:
        i += 1
return cnt ≥ p

若能配出 ≥  $p$ 对，则 D 可行。

二分答案
- 左边界 $L=0$
- 右边界 $R = A[n-1] - A[0]$
- 不断令 $\text{mid} = \lfloor(L+R)/2\rfloor$ $mid = ⌊(L + R) /2 ⌋$ ，检查可行性；
  - 若可行，则将 $R = \text{mid}-1$ ，并记录答案；
  - 否则 $L = \text{mid}+1$ 。
    结束时 $L$ 即为最小可行最大差值。

时间复杂度

排序： $O(n\log n)$
二分搜索：答案范围 $\le 10^9$ ，需 $\log(10^9)\approx 30$ 轮，每轮贪心扫描 $O(n)$
总体： $O\bigl(n\log n + n\log V\bigr),$
其中 $V = \max(A) - \min(A)$ 。

代码分解

1.预处理

对 nums 排序。

2.can_make(mid) 函数

输入：差值上限 mid
输出：布尔值，表示能否在该上限下配出 ≥ $p$ 对。
逻辑：贪心配对相邻差值 $\le$ mid 的元素。

3.二分查找主流程

初始化 $left=0$ ， $\text{right}=A[n-1]-A[0]$ 。
循环直至 $\text{left}>\text{right}$ ，更新边界并记录可行答案。

4.返回结果

最终的最小可行差值。

代码实现

from typing import List

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        # 1. 排序
        nums.sort()
        n = len(nums)

        # 2. 可行性检查函数
        def can_make(mid: int) -> bool:
            cnt, i = 0, 0
            while i < n - 1 and cnt < p:
                if nums[i+1] - nums[i] <= mid:
                    cnt += 1
                    i += 2   # 跳过已配对元素
                else:
                    i += 1
            return cnt >= p

        # 3. 二分查找最小可行差值
        left, right = 0, nums[-1] - nums[0]
        ans = right
        while left <= right:
            mid = (left + right) // 2
            if can_make(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        # 4. 返回结果
        return ans