【LeetCode】1984. Minimum difference between highest and lowest of K scores

• author ： A bright candle with snow
• id： fuxuemingzhu
• Personal blog ： http://fuxuemingzhu.cn/
• official account ： A bright candle with snow
• Key words of this article ：Leetcode, Power button , Brush problem ,Python, C++, Array , The sliding window , Difference value

---

Title Description

To give you one Subscript from 0 Start Array of integers for nums , among nums[i] It means the first one i A student's grade . I'll give you another integer k .

Select any... From the array k A student's grade , Make this k Between scores The highest and Lowest score Of Difference value achieve To minimize the .

Return possible Minimum difference .

Example 1：

 Input ：nums = [90], k = 1
 Output ：0
 explain ： elect  1  A student's grade , have only  1  Methods ：
- [90]  The difference between the highest score and the lowest score is  90 - 90 = 0
 The smallest possible difference is  0

Example 2：

 Input ：nums = [9,4,1,7], k = 2
 Output ：2
 explain ： elect  2  A student's grade , Yes  6  Methods ：
- [9,4,1,7]  The difference between the highest score and the lowest score is  9 - 4 = 5
- [9,4,1,7]  The difference between the highest score and the lowest score is  9 - 1 = 8
- [9,4,1,7]  The difference between the highest score and the lowest score is  9 - 7 = 2
- [9,4,1,7]  The difference between the highest score and the lowest score is  4 - 1 = 3
- [9,4,1,7]  The difference between the highest score and the lowest score is  7 - 4 = 3
- [9,4,1,7]  The difference between the highest score and the lowest score is  7 - 1 = 6
 The smallest possible difference is  2

Tips ：

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= 10^5

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores

The main idea of the topic

Pick anything from the array k A digital , Let this k A number of Maximum - minimum value The smallest result of .

How to solve the problem

With nums = [9,4,1,7], k = 2 For example , We see when choosing [9, 7] When these two numbers , The difference between the two figures is 2, This difference is the smallest . No matter which other two numbers you choose , Difference ratio 2 Big .
​

How to find k The difference between the maximum value and the minimum value of a number ？ It reminds us of , Sort the array , Then use a size of k Sliding window to traverse the entire array . The rightmost value of the sliding window is the maximum value in the window , The leftmost value of the sliding window is the minimum value in the window .
​

therefore , What we are looking for is an array that has been sorted , All sizes are k In the sliding window of , The rightmost digit - Leftmost digit Minimum result of .
​

C++ The code is as follows ：

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

• Time complexity ：$O(N\ast log(N))$,N Is the length of the array .
• Spatial complexity ：$O(1)$.

summary

1. about Easy subject , It is generally easy to write . The emphasis is on the abstraction of the topic .
2. Notice the border of the sliding window , Do not exceed the range of the array .

---

I am a @ A bright candle with snow , Brush algorithm questions 1000 multichannel , Yes 1000 Several algorithm solutions , Harvest reading 300 ten thousand . Pay attention to me , You won't miss my wonderful animation solution 、 Share interview questions 、 Team activity , Enter home page @ A bright candle with snow There are brush questions on the right , From then on, I'm no longer alone .

• When I brush the questions , If you don't know how to brush the questions , You can see LeetCode How should I brush ？
• If you think there are too many problems , Want to improve quickly in a short time , You can see LeetCode The most classic 100 Problem .
• Send you a code template to brush the questions ：【LeetCode】 The code template , Brush questions will

date

2022 year 2 month 11 Japan —— I just went to Sanya for a trip in the new year