1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] minutes = new boolean[24 * 60];
        int minMinute = Integer.MAX_VALUE, maxMinute = Integer.MIN_VALUE;
        for (String timePoint : timePoints) {
            String[] hourMinute = timePoint.split(":");
            int hour = Integer.parseInt(hourMinute[0]);
            int minute = Integer.parseInt(hourMinute[1]);
            int pos = hour * 60 + minute;
            if (minutes[pos]) {
                return 0;
            }
            minutes[pos] = true;
            minMinute = Math.min(minMinute, pos);
            maxMinute = Math.max(maxMinute, pos);
        }
        int prev = minMinute, ans = Integer.MAX_VALUE;
        for (int i = minMinute + 1; i <= maxMinute; i++) {
            if (minutes[i]) {
                ans = Math.min(ans, i - prev);
                prev = i;
            }
        }
        ans = Math.min(ans, 24 * 60 - maxMinute + minMinute);
        return ans;
    }
}

这道题还是值得学习一下的. 其实是find shortest distance between two elements in a circular
array的类似题型.

思路就是分配1440个slots, 因为一天就这么多minutes. 然后我们把出现的时间点都在这个slots上标记. 然后从左到右遍历即可, 就是看当前位置和上一个位置的距离是多少, 这样遍历完每个点就能知道最小的是多少. 你可能会问, 某个点到上个点的距离不一定是往左走最小, 很可能往右走绕一圈最小啊. 你说得没错, 但我们求的是最小距离, 那么绕一圈能达到最小的只能是最靠右的点绕一圈到达最左边的点. 最左和最右之间的点任意取两点, 确实它们之间的最短距离不一定就是右减左而是绕一圈, 但这也没事儿因为它们绕一圈的距离一定大于最右边点绕一圈到最左边点的距离. 因此在最左最右之间的点我们都按照右减左计算. 等到最后我们额外检查一下最右绕一圈到最左是否能达到最小, 如果能就更新一下, 不能就算了. 一个边界条件就是最右边的点到前一个点的距离要么是右减左最小, 要么是绕一圈最小. 如果上一个点不是最左边的点, 那么绕一圈会比最右边点到最左边点的距离大, 因此我们此时直接右减左计算即可. 如果刚好上一个点是最左边的点, 那么我们最后的最右减去最左绕一圈也能cover到这个case, 因此此时直接右减左计算两点距离即可.

时间复杂度: O(n) 我们parse每个point要遍历给的string list, 因此是O(n), 然后遍历最多遍历1440个slots, 这是O(1), 因此一共是O(n)
空间复杂度: O(1) 我们分配的slots长度是固定的, 就是1440个slots, 因此是O(1)