1984. Minimum Difference Between Highest And Lowest of K Scores

Easy

Description

給定整數陣列 nums 和整數 k，從中選 k 個分數，使得最高分與最低分的差值最小。回傳該最小差值。

Example:

Input: nums = [9,4,1,7], k = 2 Output: 2（選 [7,9]，差值 = 2）

Intuition#

核心思路：排序後，最小差值一定出現在連續的 k 個元素中，用固定大小的滑動視窗掃描即可。

排序後，任何一組 k 個最接近的數一定是連續的
差值 = nums[i + k - 1] - nums[i]，遍歷所有可能的起點取最小值

Approaches#

1: Brute Force - 所有組合#

概念: 嘗試所有 C(n, k) 種組合，計算每組最大最小差值
時間複雜度: O(C(n,k) * k) - 指數級
空間複雜度: O(k) - 遞迴深度

Brute Force 程式碼

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: 排序 + 固定視窗#

概念: 排序後用大小為 k 的視窗滑過陣列，取 nums[i+k-1] - nums[i] 的最小值
時間複雜度: O(n log n) - 排序主導
空間複雜度: 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: 排序 + 固定大小滑動視窗
關鍵技巧: 排序後連續子陣列的首尾差值就是該組的極差，這是處理「選 k 個元素最小化範圍」的標準手法