DeepSeek LeetCode 539. 最小时间差 Java实现

LeetCode 539. 最小时间差 - Java 实现

思路

把时间转成分钟数（HH*60 + MM），然后找这些分钟数在环形（一天 1440 分钟）上的最小间隔。

两种常用解法：

1. 排序法：排序后相邻求差，再补算首尾的环形差（首 + 1440 - 尾）。
2. 桶排序法：一天只有 1440 个分钟值，用布尔数组标记，再扫描一遍。

鸽巢原理：若 timePoints.length > 1440，必然有重复时间，直接返回 0。

解法一：排序法（推荐）

class Solution {
    public int findMinDifference(List<String> timePoints) {
        int n = timePoints.size();
        if (n > 1440) return 0;   // 鸽巢原理：必有重复

        int[] mins = new int[n];
        for (int i = 0; i < n; i++) {
            String t = timePoints.get(i);
            int h = (t.charAt(0) - '0') * 10 + (t.charAt(1) - '0');
            int m = (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
            mins[i] = h * 60 + m;
        }

        Arrays.sort(mins);

        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            minDiff = Math.min(minDiff, mins[i] - mins[i - 1]);
        }
        // 首尾跨天的环形差
        minDiff = Math.min(minDiff, mins[0] + 1440 - mins[n - 1]);

        return minDiff;
    }
}

解法二：桶排序（O(n + 1440)，无需比较排序）

class Solution {
    public int findMinDifference(List<String> timePoints) {
        int n = timePoints.size();
        if (n > 1440) return 0;

        boolean[] bucket = new boolean[1440];   // 一天 1440 分钟
        for (String t : timePoints) {
            int h = Integer.parseInt(t.substring(0, 2));
            int m = Integer.parseInt(t.substring(3, 5));
            int mins = h * 60 + m;
            if (bucket[mins]) return 0;         // 直接发现重复
            bucket[mins] = true;
        }

        int first = -1, last = -1, prev = -1, minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < 1440; i++) {
            if (!bucket[i]) continue;
            if (first == -1) first = i;
            if (prev != -1) minDiff = Math.min(minDiff, i - prev);
            prev = i;
            last = i;
        }
        // 首尾跨天
        minDiff = Math.min(minDiff, first + 1440 - last);

        return minDiff;
    }
}

示例验证

输入：[“23:59”,“00:00”]

· 转分钟：1439, 0
· 排序后：0, 1439
· 相邻差：1439 - 0 = 1439
· 首尾环形差：0 + 1440 - 1439 = 1
· 结果：1 ✅

输入：[“00:00”,“23:59”,“00:00”]

· 有重复 00:00，返回 0 ✅

复杂度分析

方法 时间复杂度 空间复杂度
排序法 O(n log n) O(n)
桶排序 O(n + 1440) O(1440)

· n 为时间点数量。桶排序在 n 较大时更优；由于一天最多 1440 种取值，n > 1440 时直接返回 0。

易错点

1. 忘了环形差：只算相邻会漏掉 “23:59” 和 “00:00” 这种跨天情况，必须补算 mins[0] + 1440 - mins[n-1]。
2. 重复时间：相同时间差为 0，排序法自然能算出（相邻差 0），桶排序要显式判断。
3. 鸽巢优化：n > 1440 时直接返回 0，既是优化也能防止意外（虽然 LeetCode 输入通常不含重复，但逻辑上要严谨）。
4. 字符串解析：用 substring + parseInt 或字符运算都行，注意冒号位置在索引 2。
   

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/m0_37843156/article/details/169563014