leetCode EASY -Q1984. Minimum Difference Between Highest and Lowest of K Scores
===

---
###### tags: `leetCode`, `練習刷題`, `1984`

<br>

## 題目

You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Example 1:

Input: nums = [90], k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
- [90]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.
Example 2:

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.

這是一個關於如何找到數組中任意連續 K 個元素的最小差值問題。具體要求是從一個整數數組中選擇 K 個連續的分數，使這些分數中的 最高分 和 最低分 之間的差異最小化。

我們可以從 《使用滑動窗口技術》的方向去進行思考：
- 排序 ：
- 首先對數組進行排序。這樣，隔壁的元素之間的差值會包含在連續的 k 個元素中的最大和最小值差值裡。
- 滑動窗口：
- 遍歷排序後的數組，維護一個大小為 K 的窗口。計算窗口中的最大值 和 最小值 的差值。
- 最新最小差值：
- 記錄下遍歷過程中遇到的最小差值。

<br>

## 解體

function minimumDifference(nums: [] , k:number){
    //如果 k 為 1 的時候，任何單個元素自己減自己，所以怎麼樣都是 0
    if(k === 1) return 0;
    
    //對array進行排列
    nums.sort((a,b) => a-b);
    
    let minDiff = Infinity; // 初始最小差值為無窮大
    
    for(let i = 0 ; i <= nums.length - k; i++){
        let currentDiff = nums[i + k -1] - nums[i];
        minDiff = Math.min(MinDiff, currentDiff);
    }
    
    return minDiff;
}

### 對 array 進行排序：
<br>

nums.sort((a,b) => a - b);

- 排序函數： 使用 array.sort() 方法將 nums 進行升序排序
- 比較函數： (a,b) => a - b 確保 array 按照數值大小升序排列。這是因為 JS 的 sort() 默認按 array 排序，所以需要指定這個比較函數來確保按數字排序。

<br>

### 初始化變量已存儲最小差值：

<br>

let minDiff = Infinity;

- 變量聲明：minDiff 用於存儲遍歷過程中遇到的最小差異。
- 初始化為無限大： 開始時將它設置為 infinity，這樣任何實現的差值都會小於它，便於後續的比較和更新。

### 遍歷數組以計算差值：

for(let i=0 ; i<nums.length -k ; i++){
    let currentDiff = nums[ i + k - 1] - nums[i];
    minDiff = Math.min(minDiff, currentDiff);
}

// 經過排序以後 [1,4,7,9]
// currentDiff = nums[i + k -1] -nums[i] 
// 就是 nums[0 + 2 - 1] = nums[1] = 4
// nums[0] = 1
// 4 - 1 = 3
// 第二演算 ： (nums[1 + 2 - 1] = nums[2] = 7) - (nums[1] = 4) === 3

<br>

- 循環控制：
- 從索引 0 開始遍歷，知道 nums.length - k. 這樣確保了從當前索引起， array 中至少還有 k 個元素，可以形成一個有效的長度為 k 的字數組。
- 計算差值：
- currentDiff 存儲當前窗口（從 i 到 i+k - 1 的子數組）中的最大值 和 最小值的差。
- 由於數組已經排序，所以最小值是 nums[i]，最大值是 nums[i+k-1]。
- 更新最小差值：
- 使用 Math.min()函數更新 minDiff ， 這個函數比較兩個數值，返回較小的那個。

<br>

## 總結

我覺得這次刷題最大的收穫應該是刷題的思維和針對array選擇index的做法。然後 k 作為次數也增加了難度。這個解法的核心在於，排序後的數組保證了連續 k 個元素是最接近的，因此檢查每個length 為 k 的窗口可以保證找到最小的最大值 與 最小值差。

希望這文章有幫助你學習！我們下篇文章再見！ PEACE！