最小时间差 图解题解

一堆 HH:MM 时间点，最小差是几分钟

给一组 "HH:MM" 格式的时间点，求任意两个时刻相差最少多少分钟。这里要留意一天是首尾相接的：23:59 和 00:00 看着隔了一整天，其实只差 1 分钟。题面例子 ["23:59","00:00"] 返回 1；["00:00","23:59","00:00"] 里有两个 00:00，返回 0。

两两都算一次差，一万个时刻要比五千万次

把每两个时刻都算一次差、取最小，能直接得到答案。可 n 个时刻有 n(n-1)/2 对，一万个就是约五千万次比较，O(n²) 在时刻一多时就撑不住。而且这么比既没用上「时间成环」这个条件，也没占到「时刻可以排序」的便宜。

化成分钟排好序，最近的两个一定挨着

先把每个 "HH:MM" 换成从零点算起的分钟数：小时乘 60 加上分钟，值落在 0 到 1439。换完从小到大排成一列，一个能省掉大半比较的性质就冒出来了：一列有序的数，差最小的两个一定相邻。若中间还夹着第三个数，那个数离两边都更近，差只会更小，自相矛盾。所以排序后只比每一对相邻的，最小差必在其中。

但这样还漏了一对。排序把最早和最晚的时刻甩到了两头，它俩在数轴上离得最远，可时间是环的：从最晚的时刻跨过午夜走到第二天最早的时刻，这段差是「最小值 加 1440 减 最大值」。这一对不落在任何相邻位置上，得单独补一刀，和所有相邻差放一起取最小才是答案。

返回全局最小，开算前还有个鸽巢特判

要比的就两类：排序后每对相邻的差，加上那一个环形差，全部取最小就是结果。参考代码用个小技巧把两类并进同一次循环——排序后往末尾补一个「最小值加 1440」当哨兵，最后一对相邻差恰好就是环形差，一行 min 全收了。

开算前还能拦一道：时刻数超过 1440 就直接返 0。一天只有 1440 个不同的 "HH:MM"，东西比坑多必有一坑装俩，超过 1440 个时刻里必然撞出两个相同的，最小差就是 0，连排序都省了。

["23:59","00:00"] 走一遍，环形差怎么救回答案

两个时刻换成分钟：23:59 是 23×60+59=1439，00:00 是 0。排序后是 [0, 1439]。相邻只有一对，1439 减 0 等于 1439，看着差了大半天。再补环形差：最小值 0 加 1440 减最大值 1439，等于 1。两者取最小，得 1。要是只比相邻、漏了环形那一对，就会错报成 1439。换成 ["00:00","23:59","00:00"]，两个 00:00 换出来都是 0，相邻差直接是 0，结果 0。

跨午夜那一对，忘补就整道错

环形那一对最容易蒸发——只扫相邻、忘了给最小值加一天，跨午夜明明很近的两个时刻会被算成隔了大半天。别退回两两暴力，排序后最近的两个已经保证相邻，全比一遍纯属白算一个平方级。还有那个鸽巢特判，时刻超过 1440 个时不加它结果照样对，但会白排一次大序。

复杂度上，换算和扫相邻都是线性的，整体落在 O(n log n)，那一次从小到大的排序是唯一超出线性的步骤；额外存 n 个分钟数外加一个哨兵，空间 O(n)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        if len(timePoints) > 1440:
            return 0
        nums = sorted(int(x[:2]) * 60 + int(x[3:]) for x in timePoints)
        nums.append(nums[0] + 1440)
        return min(b - a for a, b in pairwise(nums))

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() > 1440) {
            return 0;
        }
        int n = timePoints.size();
        vector<int> nums(n + 1);
        for (int i = 0; i < n; ++i) {
            int hours = stoi(timePoints[i].substr(0, 2));
            int minutes = stoi(timePoints[i].substr(3, 2));
            nums[i] = hours * 60 + minutes;
        }
        sort(nums.begin(), nums.begin() + n);
        nums[n] = nums[0] + 1440;
        int ans = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            ans = min(ans, nums[i] - nums[i - 1]);
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 1440) {
            return 0;
        }
        int n = timePoints.size();
        int[] nums = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            String[] t = timePoints.get(i).split(":");
            nums[i] = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
        }
        Arrays.sort(nums, 0, n);
        nums[n] = nums[0] + 1440;
        int ans = 1 << 30;
        for (int i = 1; i <= n; ++i) {
            ans = Math.min(ans, nums[i] - nums[i - 1]);
        }
        return ans;
    }
}