0949. 给定数字能组成的最大时间【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举全排列

1. 📝 题目描述

• leetcode

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。

24 小时格式为 "HH:MM"，其中 HH 在 00 到 23 之间，MM 在 00 到 59 之间。最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。

以长度为 5 的字符串，按 "HH:MM" 格式返回答案。如果不能确定有效时间，则返回空字符串。

---

示例 1：

输入：arr = [1,2,3,4]
输出："23:41"

解释：
有效的 24 小时制时间是 "12:34"，"12:43"，"13:24"，"13:42"，"14:23"，"14:32"，"21:34"，"21:43"，"23:14" 和 "23:41"。
这些时间中，"23:41" 是最大时间。

示例 2：

输入：arr = [5,5,5,5]
输出：""
解释：不存在有效的 24 小时制时间，因为 "55:55" 无效。

示例 3：

输入：arr = [0,0,0,0]
输出："00:00"

示例 4：

输入：arr = [0,0,1,0]
输出："10:00"

---

提示：

• arr.length == 4
• 0 <= arr[i] <= 9

2. 🎯 s.1 - 枚举全排列

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} arr
 * @return {string}
 */
var largestTimeFromDigits = function (arr) {
  let maxMinutes = -1

  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++) {
      if (j === i) continue
      for (let k = 0; k < 4; k++) {
        if (k === i || k === j) continue
        const l = 6 - i - j - k
        const hours = arr[i] * 10 + arr[j]
        const minutes = arr[k] * 10 + arr[l]
        if (hours < 24 && minutes < 60) {
          maxMinutes = Math.max(maxMinutes, hours * 60 + minutes)
        }
      }
    }
  }

  if (maxMinutes === -1) return ''
  const h = Math.floor(maxMinutes / 60)
  const m = maxMinutes % 60
  return `${h < 10 ? '0' + h : h}:${m < 10 ? '0' + m : m}`
}

• 时间复杂度：$O(1)$，只有 $4!=24$ 种排列
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 枚举 4 个数字的所有排列（共 24 种）
• 对每种排列检查是否构成有效的 24 小时时间（小时 < 24，分钟 < 60）
• 记录所有有效时间中的最大值