Medium

题目描述

给定一个 24 小时制的时间列表，时间格式为 “HH:MM”，返回列表中任意两个时间的最小时间差（以分钟计）。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

  • 2 <= timePoints.length <= 2 * 10^4
  • timePoints[i] 的格式为 “HH:MM”

解题思路

这道题的核心思路是将时间转换为分钟数，然后找出任意两个时间的最小差值。

主要思路：

  1. 时间转换：将每个 “HH:MM” 格式的时间转换为从 00:00 开始的分钟数。例如 “01:30” 转换为 90 分钟。

  2. 排序处理：将所有分钟数排序，这样相邻的时间差就是候选答案。

  3. 环形处理：24小时制是环形的，所以还需要考虑最大时间和最小时间的差值（跨越午夜）。例如 “23:59” 和 “00:01” 的差值应该是 2 分钟，而不是 1438 分钟。

  4. 优化剪枝：如果存在重复时间，直接返回 0。另外，一天总共只有 1440 分钟，如果时间点超过 1440 个，必然存在重复。

算法步骤：

  • 将所有时间转换为分钟数并排序
  • 计算相邻时间的差值
  • 计算跨越午夜的差值（最后一个时间到第一个时间的距离）
  • 返回所有差值中的最小值

代码实现

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> minutes;
        
        // 转换时间为分钟数
        for (const string& time : timePoints) {
            int hour = stoi(time.substr(0, 2));
            int minute = stoi(time.substr(3, 2));
            minutes.push_back(hour * 60 + minute);
        }
        
        // 排序
        sort(minutes.begin(), minutes.end());
        
        int minDiff = INT_MAX;
        
        // 计算相邻时间的差值
        for (int i = 1; i < minutes.size(); i++) {
            minDiff = min(minDiff, minutes[i] - minutes[i-1]);
        }
        
        // 计算跨越午夜的差值
        minDiff = min(minDiff, 1440 - minutes.back() + minutes[0]);
        
        return minDiff;
    }
};

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        # 转换时间为分钟数
        minutes = []
        for time in timePoints:
            hour, minute = map(int, time.split(':'))
            minutes.append(hour * 60 + minute)
        
        # 排序
        minutes.sort()
        
        min_diff = float('inf')
        
        # 计算相邻时间的差值
        for i in range(1, len(minutes)):
            min_diff = min(min_diff, minutes[i] - minutes[i-1])
        
        # 计算跨越午夜的差值
        min_diff = min(min_diff, 1440 - minutes[-1] + minutes[0])
        
        return min_diff

public class Solution {
    public int FindMinDifference(IList<string> timePoints) {
        List<int> minutes = new List<int>();
        
        // 转换时间为分钟数
        foreach (string time in timePoints) {
            string[] parts = time.Split(':');
            int hour = int.Parse(parts[0]);
            int minute = int.Parse(parts[1]);
            minutes.Add(hour * 60 + minute);
        }
        
        // 排序
        minutes.Sort();
        
        int minDiff = int.MaxValue;
        
        // 计算相邻时间的差值
        for (int i = 1; i < minutes.Count; i++) {
            minDiff = Math.Min(minDiff, minutes[i] - minutes[i-1]);
        }
        
        // 计算跨越午夜的差值
        minDiff = Math.Min(minDiff, 1440 - minutes[minutes.Count-1] + minutes[0]);
        
        return minDiff;
    }
}

var findMinDifference = function(timePoints) {
    // 转换时间为分钟数
    const minutes = timePoints.map(time => {
        const [hour, minute] = time.split(':').map(Number);
        return hour * 60 + minute;
    });
    
    // 排序
    minutes.sort((a, b) => a - b);
    
    let minDiff = Infinity;
    
    // 计算相邻时间的差值
    for (let i = 1; i < minutes.length; i++) {
        minDiff = Math.min(minDiff, minutes[i] - minutes[i-1]);
    }
    
    // 计算跨越午夜的差值
    minDiff = Math.min(minDiff, 1440 - minutes[minutes.length-1] + minutes[0]);
    
    return minDiff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
排序法O(n log n)O(n)

说明：

  • 时间复杂度：O(n log n)，主要消耗在排序操作上
  • 空间复杂度：O(n)，用于存储转换后的分钟数数组

相关题目