給定一個整數陣列
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
TIP
排序後，在答案空間 [0, max-min] 上二分搜尋最大差值，用貪心驗證是否能找到 p 對。
- 排序後，相鄰元素的差值最小，配對一定是從相鄰元素中選
- 對於給定的最大差值上限
threshold，貪心地從左到右選取差值 <= threshold 的相鄰配對 - 在答案空間上二分搜尋最小的 threshold 使得能選出 >= p 對
Approaches
1. Brute Force: Try Each Threshold Ascending — O(n log n + n·(max-min)) / O(1)
- Idea: 排序後從 0 起線性試每個差值上限，第一個能湊到 p 對的即答案
- Time:
O(n log n + n·(max-min))- 值域線性掃描、每次貪心驗證 O(n) - Space:
O(1)（不計排序）
class Solution {
fun minimizeMax(nums: IntArray, p: Int): Int {
if (p == 0) return 0
nums.sort()
val maxDiff = nums.last() - nums.first()
for (threshold in 0..maxDiff) {
if (canFormPairs(nums, p, threshold)) return threshold
}
return maxDiff
}
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
}
}⭐ 2. Binary Search on Answer + Greedy Check — O(n log n + n log(max-min)) / O(1)
- Idea: 排序後在 [0, max-min] 上二分搜尋，對每個候選值貪心檢查是否可行
- Time:
O(n log n + n log(max-min)) - Space:
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
}
}WARNING
貪心驗證的關鍵：排序後從左到右掃描，如果相鄰兩個差值 <= threshold 就配對並跳過兩個元素（i += 2），否則只跳過一個（i++）。
🔑 Takeaways
- Pattern: Binary Search on Answer + Greedy Validation
- Key trick: 「最小化最大值」是典型的二分搜尋訊號。排序 + 貪心配對相鄰元素是驗證函式的核心。注意配對後要跳過兩個元素避免重疊