What is the optimal approach to solve Minimum Difference Between Highest and Lowest of K Scores?

The optimal approach is to sort the array and use a sliding window of size k to find the minimum difference between the highest and lowest scores.

How does the sliding window technique apply to this problem?

The sliding window technique is used to efficiently check all consecutive subarrays of length k, minimizing the difference between the highest and lowest scores.

What happens when k is equal to 1 in this problem?

When k is 1, the difference between the highest and lowest scores is always 0, as there is only one score being considered.

Can the problem be solved using brute force?

While brute force is possible, it would be inefficient. Sorting and sliding window techniques provide a much more optimal solution with reduced time complexity.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) if sorting is done in place.

#1984

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

学生分数的最小差值

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。从数组中选出任意 k 名学生的分数，使这 k 个分数间最高分和最低分的差值达到最小化。返回可能的最小差值。示例 1：输入： nums = [90], …

数组滑动窗口排序

题目描述

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的差值达到 最小化 。

返回可能的 最小差值 。

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

提示：

1 <= k <= nums.length <= 1000
0 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：排序 + 滑动窗口

我们可以将学生的分数按照升序排序，然后使用滑动窗口的方法，每次取大小为 $k$ 的窗口，计算窗口内的最大值和最小值的差值，最后取所有窗口的差值的最小值。

为什么是取连续的 $k$ 个学生的分数呢？因为如果不连续，那么最大值和最小值的的差值可能不变，或者变大，但一定不会变小。因此，我们只需要考虑排序后的连续的 $k$ 个学生的分数。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是学生的数量。

1

2

3

4

5

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of sliding window technique and its connection to minimizing the difference in a sorted array.
question_mark
Solution approach emphasizes sorting and sliding window to reduce complexity, rather than brute force or nested loops.
question_mark
Candidate considers edge cases, such as when k is 1, and how the window behaves in different scenarios.

warning

常见陷阱

外企场景

error
Not sorting the array first, which would lead to incorrect results when selecting elements.
error
Misunderstanding the sliding window concept, resulting in inefficient solutions or wrong windows being chosen.
error
Incorrectly handling cases where k is equal to the length of the array, which may require special consideration.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem to find the minimum difference between highest and lowest for a subset of students based on different conditions.
arrow_right_alt
Extend the problem to find the difference for multiple windows or across multiple groups of k students.
arrow_right_alt
Modify the problem to allow for picking non-consecutive scores to minimize the difference.

help

常见问题

外企场景

继续练习

#1838 最高频元素的频数 #2271 毯子覆盖的最多白色砖块数 #1610 可见点的最大数目