LeetCode LCR 035. 最小时间差
目录
题目描述
题意分析
给一组
"HH:MM"格式的时刻，求任意两个时刻之间的最小分钟差。第一层转换很直接：字符串比较没有算术意义，
"23:59"与"00:00"按字符串看相隔很远，实际只差 1 分钟。所以第一步必须把时刻统一成一个可做减法的整数——从零点起算的分钟数，范围是[0, 1439]。第二层是「时间是循环的」。一天有 1440 分钟，
23:59与次日00:00只差 1 分钟。所以两个时刻a < b的真实差值是 $\min(b - a,\ 1440 - (b - a))$，跨零点这条路径不能忽略。第三层是取值范围带来的强信号：合法时刻只有 1440 种。如果输入超过 1440 个时刻，按抽屉原理必然存在两个完全相同的时刻，答案直接是 0。这条既是正确性的边界，也是把最坏规模压到常数的剪枝——没有它，输入可能有十万条记录，排序虽然也能过，但这条判断让复杂度上界与输入规模脱钩。
边界还包括：存在重复时刻时答案为 0；只有两个时刻时仍要考虑跨零点；全部时刻集中在一天两端时最小差恰好出现在首尾之间。
解法：排序后扫描
核心思路
暴力做法是枚举所有时刻对求差取最小，$O(n^2)$ 次比较。瓶颈很清楚：绝大多数配对根本不可能是答案——两个相距很远的时刻永远不会贡献最小值。
观察：把所有时刻按分钟数从小到大排好之后，最小差一定出现在排序后相邻的两个时刻之间。因为若
a < c < b，那么b - a必然不小于c - a与b - c，中间隔着别的元素的配对永远不可能更优。于是候选从 $O(n^2)$ 对锐减到 $n - 1$ 对。但这只覆盖了「不跨零点」的那些配对。跨零点的差值只可能出现在最大时刻与最小时刻之间（绕一圈的那段），其余任何跨零点配对都比它更长。
把这条特殊配对也并入统一扫描的技巧是：在排好序的数组末尾追加一个虚拟元素
nums[0] + 1440，表示「最小时刻在第二天的对应时刻」。这样最后一对相邻元素nums[n-1]与nums[0] + 1440的差，正好就是绕过零点的那段距离，跨零点情形被彻底吸收进同一个循环，不需要任何特判。于是不变量是：扫描到第
i个位置时，answer等于前i对相邻元素差值的最小值；扫完全部n对（含虚拟元素那一对）后，answer就是全局答案。最后再补上抽屉原理的剪枝：时刻数超过 1440 直接返回 0。这一步要放在最前面，它同时保证了后续排序的规模不会超过 1440。
解题步骤
- 抽屉剪枝：
if (timePoints.size() > 1440) return 0;。1440 是一天的分钟总数，超过就必有重复，答案为 0。放在最前面既是正确性判断，也把后续所有操作的规模钉死在常数级。- 开长度
n + 1的数组：多出来的那一格是给虚拟元素预留的，避免后面再做数组扩容或额外分支。- 解析成分钟数：按
":"切分，小时 * 60 + 分钟。统一量纲是所有时间题的第一步，之后就只剩纯整数运算。- 只对前
n个元素排序：Arrays.sort(nums, 0, n)。第n格此刻还是占位的 0，若把它一起排序会被当成一个真实的零点时刻混进来，答案会被污染。- 追加虚拟元素：
nums[n] = nums[0] + 1440，必须在排序之后赋值，因为要用的是排序后的最小值。它的语义是「最早那个时刻在第二天出现一次」，让绕零点的距离变成一次普通的相邻差。- 扫描相邻差取最小：
for (int i = 1; i <= n; ++i) answer = min(answer, nums[i] - nums[i-1])。上界写<= n才能把虚拟元素那一对算进去。初值取一个大于 1440 的数（这里是1 << 30）即可，任何真实差值都会把它替换掉。- 返回
answer。以
timePoints = ["23:59", "00:00"]走一遍。数量 2 不超过 1440。解析得nums = [1439, 0, 占位]；对前两个排序得[0, 1439, 占位]；追加虚拟元素nums[2] = 0 + 1440 = 1440，数组变成[0, 1439, 1440]。扫描：
i=1时差值1439 - 0 = 1439，answer = 1439；i=2时差值1440 - 1439 = 1，answer = 1。返回 1，与「23:59到次日00:00只差一分钟」一致。如果没有虚拟元素，答案会错成 1439。再看含重复的用例
["00:00", "23:59", "00:00"]：数量 3 未触发剪枝。解析得[0, 1439, 0]，排序前三个得[0, 0, 1439]，追加nums[3] = 0 + 1440 = 1440。扫描：i=1差值 0，answer = 0；后面两轮的差值 1439 与 1 都不会更小。返回 0，正确——重复时刻的差值天然是 0，不需要单独判重。最后看剪枝生效的情形：输入 1441 个时刻时直接返回 0，因为可用的不同时刻只有 1440 种，必然有两个撞在一起。
代码实现
class Solution {
public int findMinDifference(List<String> timePoints) {
// 抽屉原理：超过一天的分钟总数必有重复。
if (timePoints.size() > 1440) {
return 0;
}
int n = timePoints.size();
// 多留一格给「最小时刻的第二天副本」。
int[] nums = new int[n + 1];
for (int i = 0; i < n; ++i) {
String[] t = timePoints.get(i).split(":");
nums[i] = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
}
// 只排真实数据，别把占位的那一格排进来。
Arrays.sort(nums, 0, n);
// 把跨零点的差值变成一次普通的相邻差。
nums[n] = nums[0] + 1440;
int answer = 1 << 30;
for (int i = 1; i <= n; ++i) {
answer = Math.min(answer, nums[i] - nums[i - 1]);
}
return answer;
}
}
func findMinDifference(timePoints []string) int {
// 抽屉原理：超过一天的分钟总数必有重复。
if len(timePoints) > 1440 {
return 0
}
n := len(timePoints)
// 多留一格给「最小时刻的第二天副本」。
nums := make([]int, n+1)
for i, time := range timePoints {
parts := strings.Split(time, ":")
hours, _ := strconv.Atoi(parts[0])
minutes, _ := strconv.Atoi(parts[1])
nums[i] = hours*60 + minutes
}
// 只排真实数据，别把占位的那一格排进来。
sort.Ints(nums[:n])
// 把跨零点的差值变成一次普通的相邻差。
nums[n] = nums[0] + 1440
answer := 1 << 30
for i := 1; i <= n; i++ {
answer = min(answer, nums[i]-nums[i-1])
}
return answer
}
复杂度分析
- 时间复杂度：$O(n \log n)$，瓶颈在排序；解析与扫描各是一次线性遍历。由于抽屉剪枝把进入排序的元素数钉死在 1440 以内，实际运行时间与输入规模无关，可视为常数级。
- 空间复杂度：$O(n)$，用来存放转换后的分钟数组（含一格虚拟元素）。同样因为剪枝，这个数组最多 1441 个整数，实际是常数级；排序若使用递归实现还会带来 $O(\log n)$ 的栈开销。
关键点总结
- 不同格式的数据先统一量纲再计算，时间类题目一律先化成「从某个零点起算的最小单位数」，之后所有逻辑都退化成整数运算。
- 「最小差值」在排序后只可能出现在相邻元素之间，这条性质把候选从 $O(n^2)$ 对压到 $O(n)$ 对，是所有「最接近的一对」问题的通用起手式。
- 环形结构的首尾配对，用「在末尾追加
首元素 + 周期」的技巧并入普通相邻扫描，比写一个额外的特判分支更不容易漏，这个手法在环形数组、循环队列类题目里可反复复用。- 值域有限时先用抽屉原理剪枝，既处理了必然重复的边界，又把最坏规模从输入长度降到值域大小。
- 排序时要划清「真实数据」与「预留位」的边界，把占位元素一起排进去是这类「多留一格」写法的隐蔽错误。
- 面试视角：先说 $O(n^2)$ 暴力确认题意，再讲排序加相邻扫描，最后主动补上抽屉剪枝和跨零点处理。面试官常追问「能不能不排序」，答案是把 1440 个时刻做成布尔计数桶，按桶顺序线性扫描，时间降到 $O(n + 1440)$——能说出这个桶排思路是明显的加分项。
易错点总结
- 忘记跨零点的配对：
["23:59", "00:00"]只扫排序后的相邻差会得到 1439，而正确答案是 1。- 把占位格一起排序：
Arrays.sort(nums)会把第n格的 0 当成一个真实的零点时刻，["23:59", "12:00"]会因这个虚假的 0 而得到错误的更小差值。- 在排序之前就写
nums[n] = nums[0] + 1440：此时nums[0]还是输入里的第一个时刻而非最小值，["23:59", "00:00"]会算出1439 + 1440的错误虚拟点。- 漏掉抽屉剪枝：输入十万条记录时排序虽然仍能得出正确答案，但白白付出 $O(n \log n)$ 的代价，且在更严格的时限下会超时。
- 扫描上界写成
i < n：虚拟元素那一对没被计算，跨零点的差值再次丢失，["23:59", "00:00"]回到错误的 1439。- 直接比较字符串大小：
"23:59"与"00:00"按字典序相差极大，得到的差值毫无意义。- 答案初值取
1440或更小：若初值取 1440，恰好等于某些边界差值时无法区分是否被更新过；取一个明显大于 1440 的数（如1 << 30）更安全。- 解析时把小时当成分钟直接相减：
"01:30"与"02:00"会被算成差 1 而不是 30，量纲不统一导致全盘皆错。- 认为重复时刻需要单独判等：
["00:00", "00:00"]排序后相邻差自然是 0，额外的判重逻辑是多余的。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 539. 最小时间差 | 中等 | 与本题同题，可直接套用排序加环形虚拟点 |
| 1200. 最小绝对差 | 简单 | 同样靠排序后相邻扫描找最小差，但不是环形且要返回所有达到最小差的对 |
| 164. 最大间距 | 中等 | 求的是相邻最大差且要求线性时间，需要用桶划分而不能直接排序 |
| 220. 存在重复元素 III | 困难 | 差值约束外还加了下标距离约束，要用有序集合维护滑动窗口 |
| 56. 合并区间 | 中等 | 同样先排序再线性扫描相邻元素，但处理的是区间重叠而非点距 |
| 628. 三个数的最大乘积 | 简单 | 同样靠排序把最优解锁定在两端的少数候选上，避免枚举全部组合 |