How can I minimize the maximum difference of pairs in the Minimize the Maximum Difference of Pairs problem?

By sorting the array and using binary search combined with dynamic programming, you can efficiently minimize the maximum difference of pairs.

What is the time complexity of solving the Minimize the Maximum Difference of Pairs problem?

The time complexity is O(n * log V + n * log n), with n being the array length and V the range of possible differences.

Why do we need to sort the array in this problem?

Sorting ensures that adjacent numbers are as close as possible, which helps in minimizing the maximum difference in each pair.

What role does binary search play in solving the Minimize the Maximum Difference of Pairs problem?

Binary search helps find the optimal maximum difference by testing different possible values and narrowing down the most efficient solution.

How does GhostInterview assist in solving dynamic programming problems like this one?

GhostInterview guides you through the dynamic programming approach, helping you understand the state transitions involved in minimizing the maximum difference.

#2616

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最小化数对的最大差值

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

数组二分查找动态规划贪心排序

题目描述

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

lightbulb

解题思路

方法一：二分查找 + 贪心

我们注意到，最大差值具备单调性，即如果最大差值 $x$ 满足条件，那么 $x-1$ 也一定满足条件。因此我们可以使用二分查找的方法，找到最小的满足条件的最大差值。

我们可以将数组 $\textit{nums}$ 排序，然后枚举最大差值 $x$ ，判断是否存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$ 。如果存在，那么我们就可以将 $x$ 减小，否则我们就将 $x$ 增大。

判断是否存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$ ，可以使用贪心的方法。我们从左到右遍历数组 $\textit{nums}$ ，对于当前遍历到的下标 $i$ ，如果 $i+1$ 位置的数与 $i$ 位置的数的差值不超过 $x$ ，那么我们就可以将 $i$ 和 $i+1$ 位置的数作为一个下标对，更新下标对的数量 $cnt$ ，然后将 $i$ 的值增加 $2$ 。否则，我们就将 $i$ 的值增加 $1$ 。遍历结束，如果 $cnt$ 的值大于等于 $p$ ，那么就说明存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$ ，否则就说明不存在。

时间复杂度 $O(n \times (\log n + \log m))$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度，而 $m$ 是数组 $\textit{nums}$ 中的最大值与最小值的差值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        def check(diff: int) -> bool:
            cnt = i = 0
            while i < len(nums) - 1:
                if nums[i + 1] - nums[i] <= diff:
                    cnt += 1
                    i += 2
                else:
                    i += 1
            return cnt >= p

        nums.sort()
        return bisect_left(range(nums[-1] - nums[0] + 1), True, key=check)

speed

复杂度分析

指标	值
时间	O(n \cdot\log V + n \cdot\log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate understands how sorting and binary search interact to optimize the solution.
question_mark
Look for clarity in how the candidate explains the dynamic programming aspect of the problem.
question_mark
Assess whether the candidate effectively applies greedy strategies in pairing elements.

warning

常见陷阱

外企场景

error
Forgetting to sort the array first, leading to larger differences being considered.
error
Misunderstanding the binary search logic and not correctly narrowing the possible differences.
error
Pairing indices in a non-optimal way, leading to suboptimal solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjusting the value of p to see if a higher or lower number of pairs impacts the result.
arrow_right_alt
Increasing the size of nums to test for performance and handling larger arrays.
arrow_right_alt
Changing the constraints to include larger ranges of numbers or different number types.

help

常见问题

外企场景

继续练习

#2589 完成所有任务的最少时间 #2576 求出最多标记下标 #2659 将数组清空