給定整數陣列
nums和整數k，從中選k個分數，使得最高分與最低分的差值最小。回傳該最小差值。
Example:
Input: nums = [9,4,1,7], k = 2 Output: 2（選 [7,9]，差值 = 2）
Intuition
TIP
核心思路：排序後，最小差值一定出現在連續的 k 個元素中，用固定大小的滑動視窗掃描即可。
- 排序後，任何一組 k 個最接近的數一定是連續的
- 差值 =
nums[i + k - 1] - nums[i]，遍歷所有可能的起點取最小值
Approaches
1. Brute Force - All Combinations — O(C(n,k) * k) / O(k)
- Idea: 嘗試所有 C(n, k) 種組合，計算每組最大最小差值
- Time:
O(C(n,k) * k)- 指數級 - Space:
O(k)- 遞迴深度
Brute Force Code
class Solution {
fun minimumDifference(nums: IntArray, k: Int): Int {
if (k == 1) return 0
var result = Int.MAX_VALUE
fun backtrack(start: Int, chosen: MutableList<Int>) {
if (chosen.size == k) {
result = minOf(result, chosen.max() - chosen.min())
return
}
for (i in start until nums.size) {
chosen.add(nums[i])
backtrack(i + 1, chosen)
chosen.removeAt(chosen.size - 1)
}
}
backtrack(0, mutableListOf())
return result
}
}⭐ 2. Sort + Fixed Window — O(n log n) / O(1)
- Idea: 排序後用大小為 k 的視窗滑過陣列，取
nums[i+k-1] - nums[i]的最小值 - Time:
O(n log n)- 排序主導 - Space:
O(1)- 原地排序（或O(n)取決排序實作）
class Solution {
fun minimumDifference(nums: IntArray, k: Int): Int {
nums.sort()
var result = Int.MAX_VALUE
for (i in 0..nums.size - k) {
result = minOf(result, nums[i + k - 1] - nums[i])
}
return result
}
}🔑 Takeaways
- Pattern: 排序 + 固定大小滑動視窗
- Key trick: 排序後連續子陣列的首尾差值就是該組的極差，這是處理「選 k 個元素最小化範圍」的標準手法