正经题解｜最值问题

T6-最值问题

思路：

我们可以从数组选择$k$个元素，要使最大值减去最小值的差值越小越好。要让这个值最小，我们肯定要想这$k$个数挨的越近越好，那么我们可以想到先把数组进行排序。拍完序后可以使用滑动窗口来维护出最小差值。

代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int>q;
    for(int i = 1; i <= n; i ++ ){
        int x;
        cin >> x;
        q.push_back(x);
    }
    sort(q.begin(), q.end());
    int ans = 2e9 + 10;
    for(int i = 0; i + k - 1 < n; i ++ ){
        ans = min(ans, q[i + k - 1] - q[i]);
    }
    cout << ans;
    return 0;
}