LeetCode 2567. Minimum Score by Changing Two Elements
雙周賽98。這題很奇妙，第一眼沒想法就跳過不做。回來才發現被擺一道，但又沒有一次做對，又氣又好笑。
題目
輸入整數陣列nums。
-
nums的low為所有 nums[i] - nums[j] 中的最小值，其中0 <= i < j < nums.length -
nums的high為所有 nums[i] - nums[j] 中的最大值，其中0 <= i < j < nums.length - nums的總分為low和high的加總
你可以將nums中最多兩個元素改變，使得總分最小化。
求改變元素後，nums的最小可能總分。
解法
總分由low和high組成，要使總分變小可以選擇減少low或是減少high。
減少low有個穩定的方法：隨便挑選一個數字，換成某一個數字。這樣low就會是0。
減少high則可以是將nums中最小值變大，或是將最大值變小。
就拿例題二來想想：
nums = [5,3,2]
排序後 = [2,3,5]
若將最小值2變大，新的最小值肯定會是原第二小值，也就是3
若將最大值5變小，新的最大值肯定會是原第二大值，也就是3
那被改變的最大/最小值要變成多少？
nums = [2,3,5]
如果把2變3，得到[3,3,5]，high為5-3
如果把2變4，得到[3,4,5]，high為是5-3
可見最小值變成超過次小值的數並沒有意義。但是！把最小值變成次小值可以順帶把low也變成0！
赫然發現low根本是個假議題，根本不需要去管他，自然會變成0。
問題轉換成改變兩個數使high最小。
延續剛才的結論，我們可以從最小/大值下手。那如果最大值和最小值一樣怎麼辦？
nums = [1,2,3,..,5,5,5]
這種情況下改變最大值也沒用，但我們還是需要改兩個數
乾脆把最小/次小值通通變成第三小值
nums = [3,3,3,..,5,5,5]
所以最佳解必定為以下三種之一：
- 最小變成次小 + 最大變成次大
- 最小、次小變成第三小
- 最大、次大便呈第三大
最後檢查測資範圍，題目保證nums至少有三個數，因此不必擔心出界。
瓶頸在於排序，時間複雜度O(N log N)。空間複雜度O(1)。
class Solution:
def minimizeSum(self, nums: List[int]) -> int:
nums.sort()
ans=min(
nums[-2]-nums[1],
nums[-1]-nums[2],
nums[-3]-nums[0]
)
return ans