1984. 學生分數的最小差值

思路

滑動窗口入門題。

每次可以任選 $k$ 個數字，然後從這堆數字裡面拿最大跟最小取差值，這個數值要盡量小。
為了達到這個目的，將數組排序後，選擇nums[0] ~ nums[k-1]的所有數字，
這時的差值就是nums[k-1]-nums[0]。以此類推，
nums[k] - nums[1]
nums[k + 1] - nums[2]
$\dots$
在這些數值當中取最小值。就是答案。

假設現在 $k=3$，數組是 $[1,12,11,10]$，要想讓差值最小，
對於1來說，最好的選擇是10，但前提是它與10之間還有一個數字。
但沒有人在它們之間，只好退而求其次，選擇11。

排序之後的數組，$[1,10,11,12]$，數字nums[0]能考慮的只有nums[0 + k- 1]以及之後的數字， 而對它來說最好的選擇就是nums[k - 1]。

程式碼

滑動窗口

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        ranges::sort(nums);
        int n = nums.size();
        int res = INT_MAX;
        for(int i = k - 1; i < n; ++i) {
            res = min(res, nums[i] - nums[i - k + 1]);
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$，主要在排序。
• 空間複雜度：$O(1)$