LeetCode-Go 题解1984. 学生分数的最小差值排序 相邻窗口极值【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文深入解析 LeetCode 第 1984 题「Minimum Difference Between Highest and Lowest of K Scores」学生分数的最小差值围绕该题在 LeetCode-Go 仓库中的完整实现展开先给出题目语义与示例推演再推导「排序后相邻 k 个元素极值差最小」的核心结论最后结合仓库内的 Go 实现 与 单元测试 逐行讲解并给出复杂度分析。读完本文你将掌握一类「选取 k 个元素使极差最小」问题的通用套路排序 定长窗口扫描。题目描述给定一个下标从 0 开始的整数数组nums其中nums[i]表示第i名学生的分数。另给定一个整数k。从数组中选出任意 k 名学生的分数使得这 k 个分数中的最高分与最低分的差值最小化并返回这个最小差值。题目原文来自题解目录You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.Return the minimum possible difference.示例 1Input: nums [90], k 1 Output: 0 Explanation: 只有一种选法[90]最高分与最低分之差为 90 - 90 0。示例 2Input: nums [9,4,1,7], k 2 Output: 2 Explanation: 任选 2 名学生共有 6 种选法 - 选 9 和 4差值为 5 - 选 9 和 1差值为 8 - 选 9 和 7差值为 2 - 选 4 和 1差值为 3 - 选 7 和 4差值为 3 - 选 7 和 1差值为 6 最小差值为 2。约束条件1 k nums.length 10000 nums[i] 100000题目大意中文给你一个下标从 0 开始的整数数组nums其中nums[i]表示第i名学生的分数另给你一个整数k。从数组中选出任意k名学生的分数使这k个分数间最高分和最低分的差值达到最小化返回可能的最小差值。解题思路排序 相邻定长窗口核心结论答案一定来自排序后相邻的 k 个元素设选中集合的最小分数为low、最大分数为high差值定义为high - low。直觉上若要差值小选中的 k 个分数彼此应尽量靠近。严格论证如下将nums升序排序得到有序序列sorted任取一个大小为 k 的可行集合其最小值与最大值在有序序列中分别位于某个下标区间[i, j]且该区间内包含 k 个元素j i k - 1。由于序列有序区间[i, j]内的任意元素都在 low 与 high 之间因此区间极差sorted[j] - sorted[i] high - low即区间内相邻 k 个元素的选法不会比任意集合的选法差反过来任意一个排序后连续 k 个元素的选法都是合法的可行选法。所以全局最小差值必然可以在排序后所有长度为 k 的连续子数组滑动窗口中取到。于是问题被规约为求所有i满足i k - 1 n计算sorted[ik-1] - sorted[i]取最小值。这正是仓库题解文档中解题思路一节给出的两步走策略nums排序求出nums[ik-1] - nums[i]中的最小差值。复杂度分析时间复杂度O(n log n)其中n nums.length瓶颈是sort.Ints的排序开销排序后的窗口扫描是O(n)线性一趟。空间复杂度O(1)不考虑排序本身实现的内部开销只使用常数个额外变量。相比暴力枚举C(n, k)种组合k 较大时是指数级复杂度排序法把问题降到了排序的复杂度这是本题最关键的思维跃迁。Go 实现与逐行解读仓库中的完整实现位于 1984.Minimum Difference Between Highest and Lowest of K Scores.go与题解文档中给出的代码完全一致package leetcode import sort func minimumDifference(nums []int, k int) int { sort.Ints(nums) minDiff : 100000 1 for i : 0; i len(nums); i { if ik-1 len(nums) { break } diff : nums[ik-1] - nums[i] if diff minDiff { minDiff diff } } return minDiff }逐行解读sort.Ints(nums)对切片原地升序排序是后续相邻 k 个元素极差最小结论成立的前提。Go 标准库sort.Ints对int切片使用 pdqsort一种混合快速排序/插入排序/堆排序的算法在本题n 1000的数据规模下性能非常理想。minDiff : 100000 1初始值取100001刚好大于约束条件下任何可能的差值nums[i] 100000且分数非负最大差值不超过100000。也可以更稳妥地初始化为math.MaxInt32或第一个窗口的差值这里直接利用题目约束给出了一个永不干扰最小值更新的哨兵初值。窗口边界检查if ik-1 len(nums) { break }窗口右端点下标为ik-1一旦越界说明已遍历完所有长度为 k 的窗口直接终止循环避免切片越界 panic。这是实现中一个值得注意的防御性细节。diff : nums[ik-1] - nums[i]当前窗口[i, ik-1]的极差。因为数组已排序窗口内最小值就是nums[i]最大值就是nums[ik-1]。最小值更新若diff minDiff则更新最终返回minDiff即全局最小差值。边界情况验证k 1窗口长度为 1diff nums[i] - nums[i] 0任意时刻都能取到 0。对应示例 1nums [90], k 1输出 0符合只选一名学生最高分与最低分是同一人的语义。k nums.length只有一个窗口覆盖整个数组答案就是max(nums) - min(nums)循环在第一轮即可求出。单元测试与验证仓库为本题提供了配套测试 1984.Minimum Difference Between Highest and Lowest of K Scores_test.go采用 LeetCode-Go 仓库统一的参数-答案用例组织方式type question1984 struct { para1984 ans1984 } type para1984 struct { nums []int k int } type ans1984 struct { ans int }测试函数Test_Problem1984内置了两个用例恰好对应题目给出的两个示例qs : []question1984{ { para1984{[]int{90}, 1}, ans1984{0}, }, { para1984{[]int{9, 4, 1, 7}, 2}, ans1984{2}, }, }其中第二个用例[9,4,1,7], k 2还额外覆盖了输入未排序这一情况sort.Ints会先把数组排成[1,4,7,9]随后窗口依次计算4-13、7-43、9-72最终返回 2与题目示例 2 的期望输出一致。如何运行仓库根目录提供了统一的测试脚本 gotest.sh可一次性为leetcode/...下所有题目生成原子模式覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...如需单独运行本题的测试可在leetcode包目录下执行go test -run Test_Problem1984 -v ./leetcode/1984.Minimum-Difference-Between-Highest-and-Lowest-of-K-Scores/仓库模块名为github.com/halfrost/LeetCode-Go见 go.modGo 版本要求为go 1.19。举一反三这类选 k 个元素使极差最小问题的通用套路第 1984 题的解法在 LeetCode 中具有很强的通用性可抽象为以下模板排序把无序数组转成有序序列让极差与相邻元素差建立联系定长窗口扫描从小到大滑动长度为 k 的窗口用nums[ik-1] - nums[i]计算窗口极差并维护最小值答案即窗口极差最小值。同类问题还包括1030. Matrix Cells in Distance Order排序思想的另一个应用场景1846. Maximum Element After Decreasing and Rearranging同样先排序再贪心经典的**最小化最大值 / 最大化最小值**二分答案类题目如 1011. Capacity To Ship Packages Within D Days虽然思考方向不同但排序 有序性利用是共同的起点。小结本文以 LeetCode-Go 仓库的 1984 题解文档 为骨架完整覆盖了题目语义、两个官方示例、约束条件、排序 窗口的核心思路、可复制的 Go 代码、逐行解读、配套单元测试与复杂度分析。核心要点可归纳为一句话先排序再扫描所有长度为 k 的相邻窗口最小窗口极差即为答案。在n 1000的约束下O(n log n)的解法远优于组合枚举是面试与竞赛中的标准写法。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考