LeetCode 539. Minimum Time Diffe

@(LeetCode)

问题描述

给定一个时间点列表，其中时间用 24h 制来表示，格式为 HH:MM 。找出列表中两个时间点的最小间隔分钟数。

栗 1：

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

注意：

1. 列表长度为 [2, 20000]。
2. 时间点都是有效的，范围在 00:00 ~ 23:59 之间。

想看英文原文的戳这里。

解题思路

题意比较清晰，关键思路就是需要考虑到时间差的计算会有两种方向。

假设时间为 t1 和 t2，那么它们之间的路径会有如下两种。结合下图，会更好理解。

• t1->t2
• t2->t1

image.png

图中红色和蓝色分别代表不同的路径，分别表示从 00:00 -> 23:00 和 23:00 -> 00:00 的路径。（为了方便查看和理解，我把 00:00 表示为 24:00， 画到了最右端，本该是环形。）

从图中可以看出，两种路径的距离之和恰好为整个 24h 的长度：24*60=1440。因此只需计算出一个方向的差值 diff，另一个方向的差值用 1440 - diff 减去即可。

剩下的工作就是如何将时间转换成整数。这步比较简单，将小时和分钟分别解析出来，套用公式 t = 60 * h + m 即可。

举个栗子，假设时间为 23:59 和 00:00。它们的差值结果如下：

• 若时间从 00:00 ~ 23:59，则差值为 1439。
• 若时间从 23:59 ~ 00:00， 则差值为 1。

很明显，它们的最小差值为 1。

因此可以推导出如下公式来计算两个时间点的最小差值：

// 时间差
t = |t1-t2|

// 取最小值
minDiff = min(t, 1440-t)

有了以上理论基础后，解题就有眉目了。

解法

有一种比较笨的方法就是两层遍历，分别计算某个时间点与其他时间点的差值，再计算最小值。我第一种解法就是这样做的😆，但是效率不高。

下面来说下第二种解法。

先将时间点从小到大排序，这样相邻时间点之间肯定是最近的。

但是需要注意的是：

需考虑最大值和最小值之间的差值，即首尾元素。因为时间走向是环形的，最大值与最小值之间也有可能最近。

所以不仅仅是计算升序列表中前后两个元素的差值，还有首尾元素。

这里有几种实现方式：

1. 将第一个元素加上 1440 后追加到列表末尾，正常计算前后两个元素差值。
2. 遍历到最后一个元素时，与第一个比较。

下面的代码是第二种方式。

while (i < sortedTimeList.length) {
  const t1 = timeList[i]
  
  // 当为最后一个元素，与第一个比较
  const t2 = timeList[(i + 1) % sortedTimeList.length]
  const diff = calDiff(t1, t2)

  if (diff < minDiff) {
    minDiff = diff
  }

  i += 1
}

// 计算差值
var calDiff = function (t1, t2) {
  // 24 * 60
  const fullTime = 1440

  const tmp = Math.abs(t1 - t2)
  const diff = Math.min(fullTime - tmp, tmp)

  return diff
}

点此查看完整代码。

排序优化

上面的解法，我们将列表进行了排序。而排序的算法可以更加高效，使用桶排序，以空间换时间。

因为时间最大值为 1439，可以分配 1440 个桶，把列表中时间点所对应的桶填上 1。这样从头开始遍历值为 1 的元素，自然是排好序的。