LeetCode 补充题 114. 六位数字组成的最晚时间
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 949. 给定数字能组成的最大时间
:::
给你一个包含六个数字的数组
digits，请恰好使用每个位置一次，组成合法的HH:mm:ss格式时间。返回一天中最晚的合法时间。如果无法组成合法时间，返回空字符串
""。小时、分钟和秒都需要保留前导零。
示例 1：
输入：
digits = [2,3,5,9,5,9]
输出："23:59:59"
解释： 六个数字组成当天最晚的合法时间。
示例 2：
输入：
digits = [9,9,9,9,9,9]
输出：""
解释： 无法组成合法小时。
提示：
- 小时为
00…23，分钟和秒为00…59。 - 重复数字也必须按输入次数使用。
题意分析
时间比较首先看小时，再看分钟和秒，但贪心取最大的可用数字可能让剩余位置无法组成合法时间。输入固定只有六位，枚举最多
6! = 720个排列就能覆盖全部可能。
解法：枚举排列后比较一天内秒数
核心思路
[!blue]
path保存已经填好的时间位置，used[i]表示第i个输入数字是否被使用。按下标而不是数值占用资源，才能正确处理重复数字；递归返回后撤销标记，供其他排列使用。六位填满后，将相邻两位分别组成
h、m、s，只接受h < 24、m < 60、s < 60的排列。合法时间转成h * 3600 + m * 60 + s，其大小与当天先后顺序一致，所以保留最大值即可。
best初始化为 -1，将无解和合法的零点区分开。最后按两位补零格式输出；相同数字引起的重复排列不影响最大值，固定规模下无需额外去重。
解题步骤
- 按数字下标枚举六个位置的排列，允许输入值重复。
- 完整排列拆出时、分、秒，检查各自上界。
- 转换为总秒数取最大，再按两位补零格式输出。
代码实现
class Solution {
public String largestTime(int[] digits) {
int[] best = {
-1
};
dfs(digits, new boolean[6], new int[6], 0, best);
if (best[0] < 0) {
return "";
}
int value = best[0];
return String.format(
Locale.ROOT, "%02d:%02d:%02d", value / 3600, value / 60 % 60, value % 60);
}
private void dfs(int[] digits, boolean[] used, int[] path, int depth, int[] best) {
if (depth == 6) {
int h = path[0] * 10 + path[1];
int m = path[2] * 10 + path[3];
int s = path[4] * 10 + path[5];
if (h < 24 && m < 60 && s < 60) {
best[0] = Math.max(best[0], h * 3600 + m * 60 + s);
}
return;
}
for (int i = 0; i < 6; i++) {
if (!used[i]) {
used[i] = true;
path[depth] = digits[i];
dfs(digits, used, path, depth + 1, best);
used[i] = false;
}
}
}
}
import "fmt"
func largestTime(digits []int) string {
best := -1
used := [6]bool{}
path := [6]int{}
var dfs func(int)
dfs = func(depth int) {
if depth == 6 {
h, m, s := path[0]*10+path[1], path[2]*10+path[3], path[4]*10+path[5]
if h < 24 && m < 60 && s < 60 {
best = max(best, h*3600+m*60+s)
}
return
}
for i := 0; i < 6; i++ {
if !used[i] {
used[i] = true
path[depth] = digits[i]
dfs(depth + 1)
used[i] = false
}
}
}
dfs(0)
if best < 0 {
return ""
}
return fmt.Sprintf("%02d:%02d:%02d", best/3600, best/60%60, best%60)
}
复杂度分析
- 时间复杂度：六位固定输入，最多枚举 6!=720 个排列，有固定上界。
- 空间复杂度：六位固定输入，辅助空间有固定上界。
关键点总结
[!green]
六个位置最多 720 种排列，直接枚举足够；按下标标记使用情况，不能用数字值集合去重资源。
易错点总结
[!yellow]
必须检查分钟和秒的上界；00:00:00 是合法结果，不能把秒数 0 当作无解。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 949. 给定数字能组成的最大时间 | 中等 | 原题用四个数字组成时分，本题用六个数字组成时分秒，枚举下标排列并比较总秒数。 |
| 46. 全排列 | 中等 | 复用排列回溯，完整方案增加时间范围判断；相同数值仍占用不同输入位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！