LeetCode 539. 最小时间差

2024-04-26 HGNULB 约 8 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 539. 最小时间差

题意分析

给定一组 24 小时制的 HH:MM 时间点，求任意两个时间点之间的最小分钟差，返回这个最小值。

题面里藏着一个容易被忽略的定义：这些时间点都属于「一天」，而一天是首尾相接的环，不是一条线段。23:59 与 00:00 的差不是 1439 分钟，而是 1 分钟——沿着环反方向走更近。所以两个时间点之间其实有两个距离，取较小的那个。

时间点的取值范围极其有限：一天只有 24 × 60 = 1440 个不同的 HH:MM。这个「值域远小于可能的输入规模」的特征是最强的信号，它同时带来两个推论——一是可以把字符串映射成 0 到 1439 的整数，把字符串比较彻底转成整数运算；二是当输入个数超过 1440 时必有两个时间点完全相同，答案直接是 0。

输入允许重复，题目也允许两个相同的时间点配对，因此答案的下界是 0 而不是 1。这一点决定了不能写「跳过相等元素」之类的去重逻辑。

边界：至少两个时间点（只有一个无法配对，题目不会给）；00:00 与 23:59 这类跨零点的组合必须能正确处理；全部时间点相同时答案为 0。

解法：转分钟后排序

核心思路

暴力做法是两两枚举，对每一对算出两个方向的距离取小者，复杂度 $O(n^2)$。n 可以到 $2 \times 10^4$，四亿次比较必然超时，而且每次比较都要解析字符串，常数还很大。

瓶颈在于「两两枚举」枚举了大量根本不可能成为最小值的配对。突破口是：把所有时间点映射成 0 到 1439 的分钟数后排序，相隔较远的两个点之间必然夹着别的点，而夹在中间的点与两端的距离都更小。于是最小差只可能出现在排序后位置相邻的两个时间点之间，候选从 $O(n^2)$ 对骤降到 $O(n)$ 对。

但「相邻」在环上还有一对特殊情况：排序后的最后一个点与第一个点，它们在数组里离得最远，在环上却是紧挨着的邻居。把一天看成环，n 个点把环分成 n 段弧，其中 n - 1 段是数组里的相邻差，剩下那一段就是跨零点的首尾弧，长度为 1440 - last + first。答案就是这 n 段弧的最小值。

换句话说，核心结论是：排序后，环上的每一段弧恰好对应一对候选，最小时间差等于最短的那段弧。只要把这 n 段弧全部扫一遍取最小即可，一段都不能漏——尤其是那段跨零点的。

字符串到分钟的转换直接按固定位置取字符：HH:MM 的格式是定长的，第 0、1 位是小时，第 3、4 位是分钟，用 字符 - '0' 拿到数字后 hour * 60 + minute 即得。手写解析而不是调用日期库，既避开了库函数带来的解析开销，也是面试时该有的写法——考点本来就在这里。

解题步骤

逐个解析成分钟数：遍历 timePoints，把每个 HH:MM 转成 hour * 60 + minute，存进 int[] minutes。定长格式让下标可以写死，不需要 split。

排序分钟数组：Arrays.sort(minutes)。排序是「最小差只在相邻处产生」这个结论成立的前提，也是整个算法唯一的高阶开销。

初始化答案为 1440：一天总长就是任意两点差值的上界（严格来说不可能取到），拿它当初值最安全，省掉「第一次比较特判」的分支。

扫描相邻差：从 i = 1 开始，用 minutes[i] - minutes[i - 1] 更新答案。因为已排序，这个差一定非负，不需要取绝对值。存在重复时间点时该差为 0，答案自然变成 0，这正是题目要的结果。

补上跨零点的一段：1440 - minutes[n - 1] + minutes[0]，即从最大时间点跨过午夜走到最小时间点的分钟数。这是数组扫描永远覆盖不到的第 n 段弧，漏掉它就等于把环当成了线段。

返回最小值。

以 timePoints = ["23:59", "00:00", "01:39"] 走一遍。

解析：23:59 → 23 × 60 + 59 = 1439；00:00 → 0；01:39 → 1 × 60 + 39 = 99。得到 [1439, 0, 99]。
排序：[0, 99, 1439]。
初始化：ans = 1440。
i = 1：99 - 0 = 99，ans 更新为 99。
i = 2：1439 - 99 = 1340，比 99 大，ans 保持 99。
跨零点：1440 - 1439 + 0 = 1，比 99 小，ans 更新为 1。
返回 1，对应 23:59 与次日 00:00 之间的一分钟。若漏掉最后一步，会错误地返回 99，这正是本题的头号陷阱。

再看重复的情形 ["00:00", "23:59", "00:00"]：解析排序后是 [0, 0, 1439]，i = 1 时差值为 0，ans 立刻降到 0，后续任何比较都不会让它变大，返回 0——重复时间点无需任何特殊处理就能正确得出答案。

代码实现

class Solution {
    public int findMinDifference(List<String> timePoints) {
        int[] minutes = new int[timePoints.size()];
        for (int i = 0; i < timePoints.size(); i++) {
            minutes[i] = parse(timePoints.get(i));
        }
        Arrays.sort(minutes);

        int ans = 1440;
        for (int i = 1; i < minutes.length; i++) {
            ans = Math.min(ans, minutes[i] - minutes[i - 1]);
        }
        ans = Math.min(ans, 1440 - minutes[minutes.length - 1] + minutes[0]);
        return ans;
    }

    private int parse(String time) {
        int hour = (time.charAt(0) - '0') * 10 + (time.charAt(1) - '0');
        int minute = (time.charAt(3) - '0') * 10 + (time.charAt(4) - '0');
        return hour * 60 + minute;
    }
}

func findMinDifference(timePoints []string) int {
    minutes := make([]int, len(timePoints))
    for i, time := range timePoints {
        minutes[i] = parseMinute(time)
    }
    sort.Ints(minutes)

    ans := 1440
    for i := 1; i < len(minutes); i++ {
        diff := minutes[i] - minutes[i-1]
        if diff < ans {
            ans = diff
        }
    }
    wrap := 1440 - minutes[len(minutes)-1] + minutes[0]
    if wrap < ans {
        ans = wrap
    }
    return ans
}

func parseMinute(time string) int {
    hour := int(time[0]-'0')*10 + int(time[1]-'0')
    minute := int(time[3]-'0')*10 + int(time[4]-'0')
    return hour*60 + minute
}

复杂度分析

时间复杂度：$O(n \log n)$，解析是 $O(n)$、两趟扫描是 $O(n)$，量级完全由排序决定。若在开头补一句「元素个数超过 1440 直接返回 0」的鸽笼判断，参与排序的元素就不超过 1441 个，整体可以降到 $O(n)$。

空间复杂度：$O(n)$，用于存放解析后的分钟数组；排序本身在 Java 的 int[] 上是原地双轴快排，额外栈开销为 $O(\log n)$。若改用长度 1440 的计数数组代替排序，空间可以做到与输入无关的常数级。

关键点总结

先把异构数据归一成整数：把 HH:MM 映射到 0 到 1439，字符串比较的所有麻烦一次性消失。凡是「定长格式的时间/日期/坐标」，第一步都应该考虑编码成整数。

排序把 $O(n^2)$ 的配对降成 $O(n)$：只要目标是「最小差」，排序后就只需检查相邻对，因为任何非相邻对之间都夹着更近的点。这条推理对「最小绝对差」「最大间距」等一整类题通用。

环形结构要补上跨界的那一段：n 个点把环分成 n 段弧，数组扫描只能覆盖 n - 1 段。识别出「值域是环」并显式补上首尾那一段，是本题真正的考点。

值域有限意味着可以计数排序：一天只有 1440 个取值，用布尔或计数数组代替排序即可做到 $O(n)$ 时间、$O(1)$ 额外空间；顺带还能在填数组时发现重复直接返回 0。

面试视角：先说清「排序 + 相邻差 + 环形补一刀」的正确性论证（为什么最小值一定在相邻处），再主动提出鸽笼剪枝与 1440 桶的线性优化，是本题最完整的回答。面试官最常追问的两点就是「为什么只看相邻」和「23:59 到 00:00 怎么办」。

易错点总结

漏掉跨零点的那一对：只扫描排序后的相邻差，["23:59", "00:00", "01:39"] 会返回 99，而正确答案是 1。这是本题第一大错误。

跨零点写成 minutes[0] - minutes[n - 1]：方向反了，["23:59", "00:00"] 得到 0 - 1439 = -1439，返回一个负数。正确写法是 1440 - minutes[n - 1] + minutes[0]。

忘记排序就扫相邻：["23:59", "00:00", "01:39"] 解析后是 [1439, 0, 99]，minutes[1] - minutes[0] = -1439 直接把答案压成负数，且「相邻即最近」的前提根本不成立。

答案初值取 0：任何输入都会直接返回 0，因为后续只做取小操作。初值必须取不小于一天长度的上界，1440 或 Integer.MAX_VALUE 都可以。

一天的分钟数写错：把 1440 写成 1400 或 24 * 6，["23:59", "00:00"] 会算出 -39 这样的负值，跨零点那一步彻底失效。

解析时下标错位：小时取 charAt(0)、charAt(1)，分钟取 charAt(3)、charAt(4)；若把分钟写成 charAt(2)、charAt(3)，"01:39" 会拿冒号去减 '0'，解析出的分钟数完全错乱。

以为答案至少是 1 而跳过相等元素：["00:00", "00:00"] 的正确答案是 0，若写了 if (diff == 0) continue; 之类的去重，会返回 1440。

用日期库解析并做减法：LocalTime 之类的对象比较不会自动处理跨天，23:59 与 00:00 仍会算出 1439 分钟；而且这属于用库函数绕开考点，面试中会被要求手写。

相似题目

题目	难度	考察点
LCR 035. 最小时间差	中等	与本题同题，可直接套用
164. 最大间距	中等	同样看排序后的相邻差，但求最大值，且要求线性时间，需桶排序
220. 存在重复元素 III	困难	值差之外还限制下标距离，只能用有序集合或桶维护滑动窗口
56. 合并区间	中等	同为「排序后只需关心相邻元素」的套路，处理的是重叠而非差值
1010. 总持续时间可被 60 整除的歌曲	中等	同样利用值域有限做取模计数，求配对数量而非最小差
1360. 日期之间隔几天	简单	把日期编码成天数再相减，需处理闰年，不涉及环形回绕
949. 给定数字能组成的最大时间	中等	同样围绕 `HH:MM` 的合法性，靠全排列枚举而非排序扫描