最小时间差 图解题解

这道题到底在问什么

输入

timePoints=["23:59","00:00"]

输出

1 （跨午夜只差 1 分钟）

输入

timePoints=["00:00","23:59","00:00"]

输出

0 （有两个相同时间）

最优解：一步一步想明白

1. 3记住这套「换算分钟 → 排序 → 相邻求差 → 再补环形那一对」，下面每一帧都在套它。
2. 4把第 0 个时间 23:50 折算成分钟：23 小时是 1380 分钟，再加 50 分，得 1430。灰色是还没换算的，绿色是已经换好的。
3. 5把第 1 个时间 00:10 折算成分钟：0 小时是 0 分钟，再加 10 分，得 10。灰色是还没换算的，绿色是已经换好的。
4. 6把第 2 个时间 12:00 折算成分钟：12 小时是 720 分钟，再加 0 分，得 720。灰色是还没换算的，绿色是已经换好的。
5. 7把第 3 个时间 06:30 折算成分钟：6 小时是 360 分钟，再加 30 分，得 390。灰色是还没换算的，绿色是已经换好的。
6. 8把第 4 个时间 18:45 折算成分钟：18 小时是 1080 分钟，再加 45 分，得 1125。灰色是还没换算的，绿色是已经换好的。
7. 9五个时间点都换成了分钟：1430、10、720、390、1125。现在它们还是输入的乱序，下一步排序。
8. 10从小到大排好序：10、390、720、1125、1430，对应时间是 00:10、06:30、12:00、18:45、23:50。排序后，差最小的两个时间一定是挨着的，这是这套解法的根。
9. 11开始扫相邻对。两个指针指住排序后挨着的一对，从第 0、1 个起，一路往右滑。best 用来记一路见过的最小差，现在还空着。
10. 12看排序后挨着的第 0、1 个：00:10（10 分）和 06:30（390 分）。它俩相邻，差就是 390 减 10，下一帧算出来。
11. 13这一对相差 380 分钟。比之前的最小还小，best 刷新成 380。
12. 14看排序后挨着的第 1、2 个：06:30（390 分）和 12:00（720 分）。它俩相邻，差就是 720 减 390，下一帧算出来。
13. 15这一对相差 330 分钟。比之前的最小还小，best 刷新成 330。
14. 16看排序后挨着的第 2、3 个：12:00（720 分）和 18:45（1125 分）。它俩相邻，差就是 1125 减 720，下一帧算出来。
15. 17这一对相差 405 分钟。没有目前的 best=330 小，best 不变。
16. 18看排序后挨着的第 3、4 个：18:45（1125 分）和 23:50（1430 分）。它俩相邻，差就是 1430 减 1125，下一帧算出来。
17. 19这一对相差 305 分钟。比之前的最小还小，best 刷新成 305。
18. 20相邻对扫完了，但还漏了一对：排在最后的 23:50 和排在最前的 00:10。它俩看着隔了大半天，可时间是环形的，跨过午夜其实可能很近，必须补这一刀。
19. 21跨午夜的差怎么算：从最晚的 1430 分走到午夜（第 1440 分），再走到最早的 10 分，合起来是 10 加 1440 减 1430，等于 20 分钟。也就是 23:50 到第二天 00:10 只隔 20 分钟。
20. 22环形差 20 分钟，比相邻里最小的 305 还小，best 刷新成 20。这正是这道题最容易漏的一对。
21. 23扫完所有相邻对加上环形那一对，最小的是绿色高亮的这一对 23:50 和 00:10，跨午夜只差 20 分钟。答案就是 20。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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))

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问