教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇是「宫水三叶的刷题日记」刷穿 LeetCode 系列第 1984 篇题解的技术详解。文章以 LeetCode 第 1984 题「学生分数的最小差值」为线索完整讲解从「最大值最小化的二分思路」到「排序后定长窗口线性扫描」的完整推导过程并给出 Java、C、Python、TypeScript 四种语言的可直接提交代码。读完本文你将掌握「最大值最小化」类题目的二分判断范式以及「最优解必为排序后连续段」这一关键结论的证明与应用。题目描述这是 LeetCode 上的1984. 学生分数的最小差值Minimum Difference Between Highest and Lowest of K Scores难度为简单。Tag「二分」、「滑动窗口」给你一个下标从 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 10000 nums[i] 10^5数据范围很小n 1000这意味着即便使用O(n^2)的枚举也能通过但本题的价值在于其背后「最大值最小化 → 二分」与「最优解是排序后连续段 → 滑动窗口」两条通用方法论这两条方法论可以平滑迁移到n高达10^5的同类题目上后文会给出仓库中的关联题单。思路一最大值最小化问题先想二分「从n个元素里选k个使得这k个元素的最大差值最小」这是一个典型的最大值最小化问题。对于这类问题有一个非常通用的套路利用答案本身具有「二段性」将原本的求解问题转化为判断问题。具体来说我们不去直接求最小差值而是二分一个候选答案mid然后判断「是否存在一组k个分数其最高分与最低分之差不超过mid」。这里需要先解决一个关键的子问题给定候选答案x如何高效判断是否存在合法的k人组合关键结论最优的 k 个元素必然是排序后的连续段先对nums排序。可以证明若存在一组最优的k个选择那么这k个元素一定可以调整为排序后数组中的一个连续段且结果不会变差。证明反证法/调整法任取一组k个元素设它们落在排序数组中的区间为[l, r]即最小元素下标为l、最大元素下标为r则这组元素的最高分与最低分之差为nums[r] - nums[l]。现在把选择替换为排序数组中的连续k个元素例如nums[r-k1 .. r]或nums[l .. lk-1]由于替换后的区间跨度只会更小其差值一定不超过nums[r] - nums[l]。因此原问题的最优解一定可以从排序后数组的某个长度为k的连续窗口中取得。有了这个结论判断函数check(x)的实现就非常直接了只需要扫描排序后数组中所有长度为k的窗口看是否存在某个窗口满足窗口右端点 - 窗口左端点 x。二分 判定的完整实现Javaclass Solution { int[] nums; int k; public int minimumDifference(int[] _nums, int _k) { nums _nums; k _k; Arrays.sort(nums); int l 0, r 100010; while (l r) { int mid l r 1; if (check(mid)) r mid; else l mid 1; } return r; } boolean check(int x) { int n nums.length, ans nums[k - 1] - nums[0]; for (int i k; i n ans x; i) { ans Math.min(ans, nums[i] - nums[i - k 1]); } return ans x; } }实现要点说明二分上下界的选取分数范围是0 nums[i] 10^5因此任意两个分数之差的上界为10^5。代码取l 0, r 100010左闭右开地搜索最小可行差值当check(mid)成立时说明存在差值不超过mid的k人组合收缩右边界否则扩大左边界。check中的窗口遍历ans初始化为第一个窗口下标0..k-1的差值随后i从k开始遍历每次考察以nums[i]为右端点的窗口[i-k1, i]用nums[i] - nums[i-k1]更新ans。这里维护的始终是「所有大小为k的连续窗口」中的最小差值ans x作为提前退出的剪枝条件。二段性的来源若差值x可行则所有比x更大的差值也一定可行放宽约束只会让合法组合更多若x不可行则所有比x更小的差值也一定不可行。这正是可以对答案做二分的前提。思路二排序 滑动窗口O(n) 线性扫描上述二分解法中check函数本质上已经在对「所有大小为k的连续窗口」求最小差值。既然我们证明了最优解必然出现在排序后的某个长度为k的连续窗口中那么完全可以省去二分直接扫描一遍所有窗口取最小差值即为答案。这一思想正是「滑动窗口」在定长窗口场景下的应用排序后窗口左边界i-k1与右边界i同步右移每次只需要O(1)计算当前窗口内最大最小元素之差无需维护任何额外数据结构与变长窗口需要单调队列等结构不同。Java 代码class Solution { public int minimumDifference(int[] nums, int k) { Arrays.sort(nums); int n nums.length, ans nums[k - 1] - nums[0]; for (int i k; i n; i) ans Math.min(ans, nums[i] - nums[i - k 1]); return ans; } }C 代码class Solution { public: int minimumDifference(vectorint nums, int k) { sort(nums.begin(), nums.end()); int n nums.size(), ans nums[k - 1] - nums[0];; for (int i k; i n; i) ans min(ans, nums[i] - nums[i - k 1]); return ans; } };Python 代码class Solution: def minimumDifference(self, nums: List[int], k: int) - int: nums.sort() n len(nums) ans nums[k - 1] - nums[0] for i in range(k, n): ans min(ans, nums[i] - nums[i - k 1]) return ansTypeScript 代码function minimumDifference(nums: number[], k: number): number { nums.sort((a, b) a - b); let n nums.length, ans nums[k - 1] - nums[0]; for (let i k; i n; i) ans Math.min(ans, nums[i] - nums[i - k 1]); return ans; };代码逐行解读nums.sort(...)按分数升序排序。排序是整道题的前提它让「任意一组k个分数」与「排序数组中的连续窗口」建立一一对应的最小化关系ans nums[k - 1] - nums[0]初始化答案为第一个窗口即分数最低的k名学生的差值循环i从k到n-1每次滑动窗口右端点为nums[i]、左端点为nums[i - k 1]窗口内恰好包含k个元素ans Math.min(ans, nums[i] - nums[i - k 1])不断用当前窗口差值更新全局最小值循环结束后返回ans即为所有大小为k的连续窗口中的最小差值也就是题目所求。以示例 2nums [9,4,1,7]排序后为[1,4,7,9]k 2为例窗口[1,4]差值为 3[4,7]差值为 3[7,9]差值为 2答案取最小值 2与题目输出一致。复杂度分析解法时间复杂度空间复杂度二分 判定思路一排序O(n log n)二分搜索值域O(log C)C为分数值域大小每次check扫描O(n)。整体O(n log n n log C)O(log n)主要为排序所需的栈空间排序 滑动窗口思路二排序复杂度为O(n log n)遍历得到答案复杂度为O(n)。整体复杂度为O(n log n)O(log n)可以看出思路二在常数与实现复杂度上都优于思路一是本题的最优写法而思路一的「二段性 check」框架则是处理n更大、无法直接枚举窗口或需要额外判定条件的同类题目的通用武器。仓库佐证本题在刷题体系中的位置本题解收录于「宫水三叶的刷题日记」刷穿 LeetCode 系列仓库本仓库按题目编号与算法 Tag 双重组织内容仓库性质说明见 README.md。在二分专题索引 Index/二分.md 中第 1984 题被收录为推荐指数 的高性价比题目其解题路径即为「最大值最小化 → 二段性 → 二分答案」在滑动窗口专题索引 Index/滑动窗口.md 中本题同样以推荐指数 被收录归类为定长窗口的入门练习。与该题共享同一套方法论的关联题目还包括1838. 最高频元素的频数中等同样先排序再用枚举/前缀和/二分/滑动窗口组合解决「调整元素使频数最大」问题其中「排序后窗口内元素向最大值靠拢」的窗口思想与本题一脉相承1438. 绝对差不超过限制的最长连续子数组中等10^5数据范围下用「二分答案 单调队列判定」是本题「二分 check」范式在更大数据规模下的直接升级版其中关于区间长度二段性的论证可作为本题二分思路的延伸阅读1004. 最大连续1的个数 III中等、1052. 爱生气的书店老板中等、1208. 尽可能使字符串相等中等等均为「滑动窗口」Tag 下的配套练习。建议按「先掌握本题的连续段证明与定长窗口写法 → 再挑战 1438 的变长窗口 单调队列 → 最后用 1838 巩固排序 窗口的复合思路」的路线进行练习即可把本题的方法论内化为可迁移的解题能力。小结「学生分数的最小差值」是一道看似简单、实则承载了两条重要方法论的基础题最大值最小化问题优先考虑二分利用答案的二段性把「求最小可行值」转化为「判断某值是否可行」并配套check函数排序 定长滑动窗口通过反证法证明最优解必为排序数组的连续段从而用一次线性扫描O(n)直接求解替代二分是本题的最优实现。掌握这两点不仅能顺利 AC 本题更能在后续处理「最大化最小值」「最小化最大值」一类高频面试题时快速定位正确的解题框架。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode 1984 题解k 个最高分与最低分的最小差值排序 定长滑动窗口LeetCode 1984 题解k 个最高分与最低分的最小差值排序 定长滑动窗口 导读 本文围绕 LeetCode 1984「k 个最高分与最低分的最示例工程教程排序专题刷题指南LogicStack-LeetCode 排序算法题解精讲排序专题刷题指南LogicStack LeetCode 排序算法题解精讲 本文以「宫水三叶的刷题日记」刷穿 LeetCode 系列仓库中的 排序专题索引 ht教程文档LogicStack-LeetCode 刷穿系列LeetCode 16. 最接近的三数之和排序 双指针精讲LogicStack LeetCode 刷穿系列LeetCode 16. 最接近的三数之和排序 双指针精讲 本文是 LogicStack LeetCo教程文档上一篇lm-evaluation-harness 中的 Arabic PIQApiqa_ar任务阿拉伯语物理常识推理评测的配置与实现解析下一篇Fan Control不折腾BIOS调顺温度曲线的Windows风扇控制指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考