問題和演算法的步驟不再多加描述，畢竟是看了答案的思路後寫出來。主要是想記錄怎樣思考方式，想出來的解法可以在時間複雜度上跟答案差不多。
要知道任意pair的差(以下用diff表示nums[i+1] — nums[i], i=0~nums.length-1)，勢必要比較任意倆倆的數字，其時間複雜度需要O(n²)，但如果經過排序nums[i]的最小差就只能跟nums[i+1]或nums[i-1]，且時間複雜度可以降到O(n*log n)。
再來是我覺得這裡很難聯想到的地方，解題的時候可以多留意是否有存在這類的「特性」。threshold是用來計算所有diff小於等於threshold的pair數量，並且可以注意到如果diff ≤ threshold 勢必也會≤threshold+1，所以pair的數量會隨著threshold的數量增加而呈現非遞減的數列，既然已知該數列是非遞減，那剩下的就可以直接用binary search 解決了。
class Solution {
public:
int countValidPairs(vector<int> &nums, int threshold){
int count = 0;
for(size_t i=0; i<nums.size()-1; i++){
//cout << i << endl;
if(nums[i+1] - nums[i] <= threshold){
count++;
i++;
}
}
return count;
}
int minimizeMax(vector<int>& nums, int p) {
sort(nums.begin(), nums.end());
int left = -1, right = nums[nums.size()-1] - nums[0];
while(right - left > 1){
int mid = left + ((right - left) >> 1);
if(countValidPairs(nums, mid) >= p){
right = mid;
}
else{
left = mid;
}
}
return right;
}
};太習慣從題目給的條件去思考，下次可以嘗試轉換問題。例如不是從給定的p去找pair，而是從符合我要的 diff 的pair有哪些，可能就會發現非遞減的特性。
時間複雜度: O(n*log n + n*log d) where d=nums[nums.size()-1] — nums[0] (nums是排序過後的)
空間複雜度: O(1)