problem:1984. 学生分数的最小差值

思路：排序，找长度为k的每个子数组的头尾两个值即是可能得答案。

Accode:

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        deque<int> dqe;
        int len  = nums.size();
        int ans = 1e9;
        for(int i=len-1;i>=k-1;i--){
            ans = min(ans,nums[i]-nums[i-k+1]);
        }
        return ans;
    }
};

时间复杂度：$o(nlogn)$

滑动窗口版本：

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        deque<int> dqe;
        int len  = nums.size();
        int ans = 1e9;
        for(int i=0;i<len;i++){
            if(dqe.size() && i-dqe.front()+1>k) dqe.pop_front();
            dqe.push_back(i);
            if(dqe.size()>=k){
                ans = min(ans,nums[i]-nums[dqe.front()]);
            }
        }
        return ans;
    }
};

时间复杂度：同上