1984. Minimum Difference Between Highest and Lowest of K Scores

Minimum Difference Between Highest and Lowest of K Scores

題目描述： 給定一個整數陣列 nums（代表學生分數）和整數 k，從中選出 k 個分數，使得最高分和最低分的差值最小。回傳此最小差值。

解題思路：

1. 先將陣列排序。
2. 排序後，任何連續 k 個元素的組合都會有最小的極差（最大值 - 最小值）。
3. 用大小為 k 的滑動窗口掃過排序後的陣列，計算 nums[i + k - 1] - nums[i] 的最小值。

直觀理解：排序後選擇的 k 個數字越接近，差值就越小。連續的 k 個數一定比不連續的更優。

時間複雜度：O(n log n) — 排序為主要開銷，滑動窗口掃描為 O(n)。

空間複雜度：O(1) — 若不計排序內部空間，僅使用常數額外空間。

部分排序法 O(n + k log k)：使用 nth_element 找到第 k 小的元素，然後只排序前 k 小的元素。但此方法不一定能找到最優解，因為最優窗口不一定包含最小的 k 個。

暴力法 O(C(n,k) * k)：枚舉所有 k 個元素的組合，計算每組的極差。時間複雜度過高，不可行。

1. 若要選出的 k 個分數，其標準差最小（而非極差最小），做法如何？
2. 如果陣列是動態的（不斷新增分數），如何高效維護答案？
3. 如何證明最優解一定是排序後的連續子陣列？