LeetCode LCR 035. 最小时间差

约 5 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 字符串 数学 排序 LCR

题目描述

✅ LCR 035. 最小时间差

image-20260928235453798

题意分析

将每个 HH:MM 时刻看作一天中的一个位置，求任意两个位置的最短分钟间隔。一天有 1440 分钟，时间会从午夜重新开始，所以距离既可能直接相减，也可能跨过零点。

把时刻转为从零点开始的分钟数，范围为 0..1439。重复时刻的间隔为 0；可选分钟只有 1440 种，因此输入超过这个数量时必有重复，可以直接返回零。

解法：排序后扫描

核心思路

[!blue]

按分钟数排序后，先考虑不跨零点的距离。若两个时刻之间还有其他时刻，它们的距离就是若干相邻间隔之和，不可能小于其中最小的相邻间隔。因此只需扫描相邻时刻，不必枚举所有配对。

跨零点的候选也只需保留最大时刻到最小时刻这一段。任何其他跨零点的路径都会在这段之外再增加一些距离，所以不会更短。将这个首尾间隔与普通相邻间隔一起比较，即可覆盖全局最小值。

代码在数组末尾预留一格，排序真实时刻后放入 nums[0] + 1440，表示最小时刻的次日位置。最后一对相邻差就是跨零点距离，于是一个循环可以统一扫描全部环形间隔。

抽屉原理的数量检查放在解析和排序之前：超过 1440 项立即返回零，其余输入才继续处理。没有触发这条检查的重复时刻，也会在排序后产生相邻零间隔。

解题步骤

  1. 若时刻数量大于 1440，返回 0；否则创建长度为 n + 1 的分钟数组。
  2. 将前 n 项转换为“小时 × 60 + 分钟”。
  3. 只排序前 n 项真实数据，不能把尚未赋值的预留格参与排序。
  4. 将最后一格设为排序后的最小值加 1440。
  5. 从下标 1 扫描到 n，比较所有相邻差，返回最小值。

代码实现

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 answer = 1 << 30;

        for (int i = 1; i <= n; ++i) {
            answer = Math.min(answer, nums[i] - nums[i - 1]);
        }

        return answer;
    }
}

import (
    "sort"
    "strconv"
    "strings"
)

func findMinDifference(timePoints []string) int {
    // 抽屉原理：超过一天的分钟总数必有重复。
    if len(timePoints) > 1440 {
        return 0
    }

    n := len(timePoints)
    // 多留一格给「最小时刻的第二天副本」。
    nums := make([]int, n+1)
    for i, time := range timePoints {
        parts := strings.Split(time, ":")
        hours, _ := strconv.Atoi(parts[0])
        minutes, _ := strconv.Atoi(parts[1])
        nums[i] = hours*60 + minutes
    }

    // 只排真实数据，别把占位的那一格排进来。
    sort.Ints(nums[:n])
    // 把跨零点的差值变成一次普通的相邻差。
    nums[n] = nums[0] + 1440

    answer := 1 << 30
    for i := 1; i <= n; i++ {
        answer = min(answer, nums[i]-nums[i-1])
    }

    return answer
}

复杂度分析

  • 时间复杂度：n <= 1440 时为 $O(n\log n)$，排序占主导，解析与扫描为线性；n > 1440 时读取长度后直接返回，为 $O(1)$。
  • 空间复杂度：进入排序时为 $O(n)$，保存最多 1441 个整数；直接返回分支只使用 $O(1)$ 额外空间。

关键点总结

[!green]

  • 排序后的相邻间隔加上首尾间隔，覆盖了圆周上的全部最短距离候选。
  • 最小值加一整天的虚拟元素，把跨零点距离统一为普通相邻差。
  • 有限分钟数允许先用抽屉原理处理必然重复的输入。

易错点总结

[!yellow]

  • 只扫描真实数组中的相邻项，会漏掉最大、最小时刻之间跨零点的间隔。
  • 数量检查是大于 1440，不是大于等于；恰好 1440 个时刻仍可能全部不同。
  • 必须先排序真实数据，再写入最小值的次日副本，否则占位零值可能污染结果。
  • 扫描上界要包含虚拟元素下标 n；重复时刻会自然产生零间隔，无需特殊配对。

相似题目

题目 难度 关联与区别
1200. 最小绝对差 简单 同样排序后只比较相邻差值，本题时间是环，还需比较末项到次日首项。
164. 最大间距 中等 同样把间距问题转成有序相邻元素关系，原题取最大间距，本题取最小环形间距。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/85593233
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！