Description
給定一個整數陣列
nums和整數p。從陣列中選出p對不重疊的索引對，使得這p對中最大差值最小化。回傳這個最小化後的最大差值。
Example:
Input: nums = [10,1,2,7,1,3], p = 2 Output: 1（選 (1,4) 和 (2,5)，差值分別為 0 和 1，最大差值為 1）
Intuition#
排序後，在答案空間 [0, max-min] 上二分搜尋最大差值，用貪心驗證是否能找到 p 對。
- 排序後，相鄰元素的差值最小，配對一定是從相鄰元素中選
- 對於給定的最大差值上限
threshold，貪心地從左到右選取差值 <= threshold 的相鄰配對 - 在答案空間上二分搜尋最小的 threshold 使得能選出 >= p 對
Approaches#
1: Binary Search on Answer + Greedy Check#
- 概念: 排序後在 [0, max-min] 上二分搜尋，對每個候選值貪心檢查是否可行
- 時間複雜度:
O(n log n + n log(max-min)) - 空間複雜度:
O(1)（不計排序空間）
class Solution {
fun minimizeMax(nums: IntArray, p: Int): Int {
if (p == 0) return 0
nums.sort()
var left = 0
var right = nums.last() - nums.first()
while (left < right) {
val mid = left + (right - left) / 2
if (canFormPairs(nums, p, mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
private fun canFormPairs(nums: IntArray, p: Int, threshold: Int): Boolean {
var count = 0
var i = 0
while (i < nums.size - 1) {
if (nums[i + 1] - nums[i] <= threshold) {
count++
i += 2 // 跳過已配對的兩個元素
} else {
i++
}
if (count >= p) return true
}
return count >= p
}
}貪心驗證的關鍵：排序後從左到右掃描，如果相鄰兩個差值 <= threshold 就配對並跳過兩個元素（
i += 2），否則只跳過一個（i++）。
🔑 Takeaways#
- Pattern: Binary Search on Answer + Greedy Validation
- 關鍵技巧: 「最小化最大值」是典型的二分搜尋訊號。排序 + 貪心配對相鄰元素是驗證函式的核心。注意配對後要跳過兩個元素避免重疊