LeetCode 949. 给定数字能组成的最大时间
目录
题目描述
题意分析
给定恰好四个 0 到 9 的数字，要求把它们全部用上、每个用一次，摆成 24 小时制的
HH:MM形式，返回能摆出的最晚时刻；一个都摆不出来就返回空字符串。「最晚」是按时间先后比，不是按数字大小随便比。合法性有两道硬门槛：前两位组成的小时必须落在 0 到 23，后两位组成的分钟必须落在 0 到 59。注意
04:20这类以 0 开头的时刻是完全合法的，所以不能像普通数字那样嫌弃前导零。约束里最强的信号是数组长度恒为 4。四个元素的排列一共只有 $4! = 24$ 种，这个规模小到可以把所有摆法都试一遍，任何精巧的贪心或剪枝在这里都是负收益。
边界上要留意两点：数组里的数字允许重复（比如四个 5），所以「每个数字用一次」指的是每个位置用一次，去重必须按下标而不是按数值；另外确实存在一个合法时刻都摆不出来的输入，必须返回空字符串而不是某个默认值。
解法：枚举全排列并记录最大分钟数
核心思路
面对「找最优摆法」这类问题，本能反应往往是贪心：先让小时尽可能大，再让分钟尽可能大。但贪心在这里需要额外论证——小时取到最大之后，剩下两个数字未必能凑出合法的分钟，一旦不能就得回退，回退逻辑写起来比穷举还啰嗦。
真正的突破口不在算法而在规模：输入长度被钉死为 4，全排列只有 24 种。这意味着「暴力」在这道题里不是退而求其次的方案，而是最优方案——它没有瓶颈可言，正确性一目了然，也没有任何需要证明的贪心性质。识别出「数据规模已经小到让穷举成为首选」，本身就是这道题要考的判断力。
于是问题变成如何干净地枚举 24 种排列。四个位置各用一层循环枚举它们取自原数组的哪个下标，靠「下标互不相同」这一条约束把 $4^4 = 256$ 种取法过滤成 24 种真排列。之所以按下标而非按数值去重，是因为输入允许出现相同数字，按数值去重会把
[0,0,0,0]这种输入的全部摆法误杀掉。最后一个设计点是「如何比较两个时刻的先后」。把时刻拆成小时和分钟两个字段去比较，需要写嵌套判断；转成字符串比较则要先处理补零。更干净的办法是把每个合法时刻归一化成从零点起算的总分钟数
hour * 60 + minute，于是「时刻更晚」严格等价于「这个整数更大」，比较退化成一次取最大值。这样就得到贯穿全程的不变量：变量
best始终等于「已枚举过的排列中，所有合法时刻对应的总分钟数的最大值」；若一个合法时刻都还没遇到，best保持哨兵值 -1。由于任何合法时刻的总分钟数都非负，-1 不会和真实答案混淆，用它区分「无解」和「零点」既安全又省一个布尔变量。
解题步骤
- 令
best = -1作为哨兵。为什么不用 0：00:00是一个合法时刻，它的总分钟数正是 0，用 0 当哨兵就无法区分「无解」和「答案是零点」。- 用四层循环分别枚举小时十位、小时个位、分钟十位、分钟个位取自原数组的下标
i、j、k、l，每层进入时跳过与外层已用下标相同的取值。为什么按下标去重：数组里可以有相同数值，按数值跳过会让[0,0,0,0]这类输入一种摆法都剩不下。- 在最内层算出
hour = arr[i] * 10 + arr[j]与minute = arr[k] * 10 + arr[l]。为什么前两位是小时：HH:MM的格式固定，这一步只是把排列翻译成时刻。- 仅当
hour < 24且minute < 60时，才用hour * 60 + minute去更新best。为什么用严格小于：小时的合法上界是 23、分钟是 59，写成小于等于会放进24:00、23:60这类不存在的时刻。为什么必须放在if内更新：非法组合一旦参与取最大值，就会污染答案。- 循环结束后若
best仍是 -1，说明 24 种排列无一合法，返回空字符串。- 否则用
best / 60还原小时、best % 60还原分钟，各自拆成十位和个位输出，保证两位数补零。为什么必须手动补零：小时可能是个位数，直接输出会得到9:00这种不符合HH:MM格式的串。以
arr = [1,2,3,4]走一遍：best初值 -1。枚举到
i=0, j=1（数字 1 和 2）时小时是 12，剩下的两个下标能组成分钟 34 或 43，都小于 60，于是best先后被更新为 $12 \times 60 + 34 = 754$ 和 $12 \times 60 + 43 = 763$。枚举到
i=0, j=2时小时是 13，分钟候选 24 与 42 均合法，best升到 $13 \times 60 + 42 = 822$。枚举到
i=1, j=0时小时是 21，分钟候选 34 与 43，best升到 $21 \times 60 + 43 = 1303$。枚举到
i=1, j=2时小时是 23，剩下数字 1 和 4，分钟候选 14 与 41，两者都小于 60，best升到 $23 \times 60 + 41 = 1421$。剩下的排列里，凡是小时十位取到 3 或 4 的（小时至少是 31）全部被
hour < 24挡掉；小时取 14、24 之类的组合，要么小时超界，要么剩余数字组成的分钟不小于 60（如小时 12 之后分钟只能是 34、43，已算过）。整轮枚举结束，best停在 1421。还原输出：$1421 / 60 = 23$，$1421 \bmod 60 = 41$，小时拆成
2和3、分钟拆成4和1，拼出"23:41"。再看无解的场景：
arr = [5,5,5,5]，唯一可能的小时是 55、唯一可能的分钟也是 55，hour < 24从未成立，best全程保持 -1，返回空字符串。
代码实现
class Solution {
// 一个排列的前两位组成小时、后两位组成分钟，合法条件是小时小于 24 且分钟小于 60。
public String largestTimeFromDigits(int[] arr) {
int best = -1;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (j == i) {
continue;
}
for (int k = 0; k < 4; k++) {
if (k == i || k == j) {
continue;
}
for (int l = 0; l < 4; l++) {
if (l == i || l == j || l == k) {
continue;
}
int hour = arr[i] * 10 + arr[j];
int minute = arr[k] * 10 + arr[l];
if (hour < 24 && minute < 60) {
best = Math.max(best, hour * 60 + minute);
}
}
}
}
}
if (best == -1) {
return "";
}
int hour = best / 60;
int minute = best % 60;
return "" + hour / 10 + hour % 10 + ":" + minute / 10 + minute % 10;
}
}
func largestTimeFromDigits(arr []int) string {
// 一个排列的前两位组成小时、后两位组成分钟，合法条件是小时小于 24 且分钟小于 60。
best := -1
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
if j == i {
continue
}
for k := 0; k < 4; k++ {
if k == i || k == j {
continue
}
for l := 0; l < 4; l++ {
if l == i || l == j || l == k {
continue
}
hour := arr[i]*10 + arr[j]
minute := arr[k]*10 + arr[l]
if hour < 24 && minute < 60 {
candidate := hour*60 + minute
if candidate > best {
best = candidate
}
}
}
}
}
}
if best == -1 {
return ""
}
return formatTime(best)
}
func formatTime(minutes int) string {
hour := minutes / 60
minute := minutes % 60
return string([]byte{
byte('0' + hour/10),
byte('0' + hour%10),
':',
byte('0' + minute/10),
byte('0' + minute%10),
})
}
复杂度分析
- 时间复杂度：$O(1)$，输入长度恒为 4，四层循环合计 $4^4 = 256$ 次迭代，其中只有 $4! = 24$ 次通过下标去重进入判定，每次判定是常数次算术，与任何变量无关。
- 空间复杂度：$O(1)$，只用了
best和几个循环变量，输出串长度固定为 5，没有任何随输入增长的结构。
关键点总结
- 先看数据规模再选算法。当输入长度被题目钉死在一个极小的常数上时，穷举不是妥协而是最优解——它省掉了贪心正确性的证明负担，白板上也最不容易出错。
- 「用完给定元素的每一个」这类要求，去重维度是位置而不是数值。只要输入允许重复元素，按值去重就是一个系统性错误。
- 把带结构的比较对象归一化成单个可比的标量（这里是从零点起算的总分钟数），能让「取最优」退化成一次
max，同时消灭补零、字段优先级这些干扰项。- 用哨兵值区分「无解」时，必须确认哨兵落在合法答案的取值范围之外。这里 -1 可以而 0 不行，因为零点是合法答案。
- 面试视角：一上来先说清「只有 24 种排列，直接枚举」，把规模判断显式讲出来，比闷头写贪心更能拿分；如果面试官追问贪心行不行，可以指出「小时取最大后剩余数字未必能组成合法分钟」，需要回退，反而更复杂。
- 面试视角：这题的实现分会集中在两处细节——按下标去重和输出补零。写完主动用
[0,0,0,0]和[5,5,5,5]各自口头验一遍，正好覆盖这两个坑加上无解分支。
易错点总结
- 错误写法：内层循环按数值去重，写成
if (arr[j] == arr[i]) continue;。用例[0,0,0,0]→ 所有摆法都被当作重复跳过，返回空字符串，正确答案是"00:00"。- 错误写法：
best初始化为 0 而不是 -1。用例[5,5,5,5]→ 无解时best仍是 0，被当成零点输出"00:00"，正确答案是空字符串。- 错误写法：合法性判断写成
hour <= 24 && minute <= 60。用例[2,4,0,0]→ 小时 24、分钟 00 通过检查，总分钟数 1440 压过合法的20:40，输出"24:00"这个不存在的时刻。- 错误写法：把
best的更新写在合法性判断之外。用例[5,5,5,5]→ 非法组合 55 时 55 分也参与取最大，输出"55:55"，正确答案是空字符串。- 错误写法：四层循环之间不做下标互斥检查。用例
[1,0,0,0]→ 下标 0 被重复取用，摆出11:11（用了两个 1，可原数组只有一个），正确答案是"10:00"。- 错误写法：只枚举小时用的两个下标，分钟直接按剩余元素在数组中的原顺序拼接。用例
[1,9,6,0]→ 小时 19 时剩余顺序拼出 60 被判非法而丢弃了这个小时，最终输出"09:16"，正确答案是"19:06"。- 错误写法：输出时不补零，直接把小时和分钟当整数拼进字符串。用例
[0,9,0,0]→ 得到"9:0"而不是"09:00"，格式不合要求。- 错误写法：以
hour * 60 + minute存储best，还原时却按best / 100和best % 100拆分。用例[1,2,3,4]→best是 1421，被拆成 14 时 21 分，输出"14:21"，正确答案是"23:41"。- 错误写法：以为把四个数字降序拼起来就是答案。用例
[1,2,3,4]→ 得到"43:21"，小时越界，正确答案是"23:41"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 46. 全排列 | 中等 | 元素互异，用递归模板输出全部排列而非挑最优 |
| 47. 全排列 II | 中等 | 元素可重，需排序后同层跳过相同值来避免重复方案 |
| 31. 下一个排列 | 中等 | 原地推出字典序的下一个，靠单调性定位而非枚举 |
| 556. 下一个更大元素 III | 中等 | 在排列变换之外还要处理 32 位整数溢出与无解返回 -1 |