Leetcode 2616. Minimize the Maximum Difference of Pairs

[Woodyiiiiiii]

2616. Minimize the Maximum Difference of Pairs这道题的难点在于使用什么方法。

首先我想的是排序后用堆记录所有相邻的Pair，然后每取一次Pair后向堆中加入新的Pair，但问题是如果出现相同距离的Pair，就不知道取哪个Pair好了，因为取的Pair不同对后续的Pair有影响；那么考虑用DP来比较呢，也发现不现实。

那这里看到最大化最小值/最小化最大值类型题目条件，就考虑下用二分+贪心了，因为满足单调性，如果a满足，那么a+1也能满足。二分后，就是尽量多的计算数组中的对数是否大于等于p了。

然后问题变成，如何取Pair呢，而且是在O(n)时间复杂度下。这种情况下只能用DP或者贪心了。首先考虑贪心。

假设(a1, a2, a3, a4)，我想过如果取a2,a3，那接下来要取a1a4怎么办，但实际上，既然a1a4可以。那么何妨不去a1a2和a3a4呢？所以可以按照顺序从左到右取数组内的Pair了。

接着，假如a1a2可以，需不需要取呢？这里引入归纳法，假设取a1a2，那么答案就是f(n-2)+1，反之则是f(n-1)；为了比较两者的大小，继续归纳，f(n-1)肯定小于等于f(n-3)+1，而f(n-2)大于等于f(n-3)，所以可以得到f(n-2)+1 >= f(n-1)。最后结论就是从左到右遍历时发现如果Pair满足，则直接取即可。

class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int l = 0, r = (int)1e9+1;
        while (l < r) {
            int m = (l+r)>>1;
            if (ok(nums, p, m)) {
                r = m;
            } else {
                l = m+1;
            }
        }
        return l;
    }

    private boolean ok(int[] nums, int p, int m) {
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i+1] - nums[i] <= m) {
                ++cnt;
                ++i;
            }
        }
        return cnt >= p;
    }
}

func minimizeMax(nums []int, p int) int {
	// sort the array
	sort.Ints(nums)
	l := 0
	r := nums[len(nums)-1] - nums[0]
	for l < r {
		m := (l+r) >> 1
		if ok(nums, m, p) {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

func ok(nums []int, m, p int) bool {
	cnt := 0
	for i := 0; i < len(nums)-1; i++ {
		if nums[i+1]-nums[i] <= m {
			cnt++
			i++
		}
	}
	return cnt >= p
}

其实也可以用DP，同样是O(n)的思路。

类似的二分题目集合：

• 我的总结
• [Java/C++/Python] Binary Search
• 二分答案 + 贪心，附题单（Python/Java/C++/Go）