LeetCode 539. 最小时间差

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 华为
标签
数组 字符串 数学 排序

题目描述

✅ 539. 最小时间差

image-20260928235801540

题意分析

求列表中任意两个时间点的最小分钟差。一天有 1440 分钟，时间会在午夜回到零点，所以两点之间可以沿当天顺序计算，也可以跨午夜计算，取较短的一段。

先把 HH:MM 转换成零点后的分钟数 hour * 60 + minute，所有时间就落在 0 到 1439 之间。之后只需比较整数距离，避免混用小时和分钟。

解法：转分钟后排序

核心思路

[!blue]

把一天看成一个圆，排序后的分钟数是各个点沿圆周的先后顺序。任意两点之间的一段弧，如果中间还有其他时间点，就会被拆成若干相邻间隔，其中至少一个不会比整段弧更长。因此，最小时间差一定能在圆周相邻的两个点之间找到，无需枚举所有点对。

将圆在零点处切开后，排序数组里的 n - 1 对相邻元素只覆盖不跨午夜的间隔，它们的差是 minutes[i] - minutes[i - 1]。最后一个时间点到第一个时间点也是圆周上的相邻关系：先走到午夜需要 1440 - last 分钟，再从零点走到 first，所以还要比较 1440 - last + first。

这 n 个间隔覆盖了圆周上所有相邻关系，取其中最小值即可。尤其当只有两个时间点时，普通相邻差和首尾差恰好对应两种方向，所以跨午夜更近的情况也能正确处理。

ans 保存目前已经检查过的最小间隔，从 1440 开始逐次缩小。重复时间在排序后相邻，差值为零；零已经是最小可能值，后续取最小值不会改变它，因此不需要去重，也不能把重复时间删除。

解题步骤

  • 将小时乘六十并加分钟。
  • 排序后比较全部 n-1 个相邻差。
  • 再比较首尾跨午夜的间隔。

题目保证至少有两个时间点，且字符串是合法的 HH:MM 格式，因此可以直接读取下标 0、1 的小时数字和 3、4 的分钟数字；每个字符减去 '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;
    }
}

import "sort"

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)$，保存分钟数组。

关键点总结

[!green]

  • 一天是一个圆，首尾也是相邻点。
  • 重复项保留，零就是可能的最小答案。

易错点总结

[!yellow]

  • 漏算首尾会将二十三点五十九分与零点误判为相差一千四百三十九分钟。
  • 小时直接与分钟相加，单位不一致。

相似题目

题目 难度 关联与区别
1200. 最小绝对差 简单 同样排序后只比较相邻差值，本题时间是环，还需比较末项到次日首项。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/36762315
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！