📃 题目描述

题目链接：

• 剑指 Offer II 035. 最小时间差 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 539. 最小时间差 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

这个题目最直观的解法是求出任意两个时间的间隔，然后比较得出最小的时间差。如果输入 n 个时间，那么需要计算每个时间与另外n-1个时间的间隔，这种蛮力法需要O（n2）的时间。

上述解法的一个优化方法是把 n 个时间排序。排序之后只需要计算两两相邻的时间之间的间隔，这样就只需要计算O（n）个时间差。由于对 n 个时间进行排序通常需要O（nlogn）的时间，因此这种优化算法的总体时间复杂度是O（nlogn）。

这里有一个特殊情况值得注意。如果把输入的时间数组 ["23：50"，"23：59"，"00：00"] 排序，就可以得到["00：00"，"23：50"，"23：59"]：

时间 00：00 和 23：50 之间的间隔是 1430 分钟，而 23：50 和 23：59 之间的间隔是 9 分钟。

⭐ 由于排序之后的第 1 个时间 00：00 也可能是第 2 天的 00：00，它和前一天的 23：59 之间的间隔只有1分钟。也就是说，在计算最小时间差时，需要把排序之后的第 1 个时间当作第 2 天的时间（即加上 24 小时）与最后一个时间之间的间隔也考虑进去。

再举个例子

比如 01:00(t1) 和 23:00(t2)：

• 情况 1：如果这俩是同一天，那么相差 22 个小时（这种情况肯定需要考虑的，没得说）
• 情况 2：如果 t1 在第二天，t2 在第一天，那么 t2 再经过 2 个小时就能到 t1 时间（这种情况需要考虑）
• 情况 3：如果 t1 在第一天，t2 在第二天，那么 t1 还需要 23 + 23 = 46 个小时才能到达 t2（这种情况显然不用考虑了）

接着思考如何做进一步优化。前面的算法主要将时间花在排序上面，那么排序是否可以避免？排序是为了计算相邻的两个时间的节点，所以用一个表示时间的数组也可以达到这个目的。

一天有24小时，即1440分钟。如果用一个长度为1440的数组表示一天的时间，那么数组下标为0的位置对应时间00：00，下标为1的位置对应时间00：01，以此类推，下标为1439的位置对应23：59。数组中的每个元素是true或false的标识，表示对应的时间是否存在于输入的时间数组中。

有了这个辅助数组，就只需要从头到尾扫描一遍，相邻的两个为 true 的值表示对应的两个时间在输入时间数组中是相邻的。例如，输入时间数组["23：50"，"23：59"，"00：00"]，数组中只有下标为 0、1430和1439 这3个位置的值为true，其他位置的值都是 false。

由于数组的下标对应的是时间，因此两个时间之间的时间差就是它们在数组中对应的下标之差

class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] times = new boolean[1440];
        for (String timePoint : timePoints) {
            int minutes = transfer(timePoint);
            // 如果 times[minutes] 已经置为 true, 说明出现了两个一样的时间，直接返回 0 就行了
            if (times[minutes] == true) {
                return 0;
            }
            times[minutes] = true;
        }

        int minLen = times.length - 1;
        // 这个字段用来计算第 1 种情况（在同一天），两个连续时间 当天 的时间差
        int pre = -1;
        // 这两个字段是用来计算第 2 种情况的（不在同一天），第一天的时间要尽可能大，第二天的时间要尽可能小
        int first = -1; // 第一天
        int last = times.length - 1; // 第二天
        for (int i = 0; i < times.length; i ++) {
            if (times[i] == true) {
                if (pre != -1) {
                    minLen = Math.min(minLen, i - pre);
                }
                
                pre = i;
                // 第一天时间尽可能大
                first = Math.max(first, i);
                // 第二天时间尽可能小
                last = Math.min(last, i);
            }
        }

        return Math.min(minLen, last + times.length - first);
    }

    // hour -> minutes
    private int transfer(String timePoint) {
        String[] item = timePoint.split(":");
        return Integer.parseInt(item[0]) * 60 + Integer.parseInt(item[1]);
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)