Problem#
給你一個整數陣列 nums 你可以從中挑一個數字將其改寫成另一個數字，要操作三次，問你操作完時，陣列中最大的數字和最小的數字之「差」最小是多少?
測資限制#
- $1 \le n \le 10^5$
- $-10^9 \le val \le 10^9$
想法#
- 可以將「改寫數字」轉化成「刪除數字」: 因為你想改寫一定不會想要改成更大或更小的數字(這樣答案就變大了)，但答案還是受限於目前最大和最小的數字，意思是改寫數字本身相當無將該數字從陣列中刪除一樣
- 從範例2，可以觀察出答案是
num[n-1 - 3] - num[0]- 反例
[0,1,1,4,6,6,6]上面的方法就無效，但真的完全無效嗎?
- 反例
- 我們不是刪除最大數字，就是刪除最小的數字，這樣答案才會變小，總共要刪除 $3$ 個數字，因此可以試過所以刪除最大最小的組合: 刪除「$3$大$0$小」、「$2$大$1$小」、「$1$大$2$小」、「$0$大$3$小」。
- 全部都試過，找最小的差就是答案
- 邊界可以先定義好: 如果陣列的數字 $\le 4$ 答案就是 $0$: $n = 4$，刪去 $3$ 個數字剩下 $1$ 個數字； $n \le 3$，可以把數字全部刪完。
AC Code#
- 時間複雜度: $\mathcal{O}(n\log{n})$
- 空間複雜度: $\mathcal{O}(1)$
心得#
原本還寫成模擬的，太醜了就不貼上來了