LeetCode 949. 给定数字能组成的最大时间

约 6 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 网易
标签
数组 字符串 回溯 枚举

题目描述

✅ 949. 给定数字能组成的最大时间

image-20260928225354644

image-20260928225354645

题意分析

给定四个 0 到 9 的数字，每个数组位置恰好使用一次，组成一个 24 小时制时间，返回其中最晚的合法时间。小时必须在 00 到 23，分钟必须在 00 到 59，输出固定为五个字符的 HH:MM。

数字可以重复，相同数字来自不同位置时仍各有一次使用机会。没有合法排列时返回空字符串；零点是合法时间，不能与无解混淆。

解法：枚举全排列并记录最大分钟数

核心思路

[!blue]

输入固定只有四个位置，总共只有 4! = 24 种下标排列，直接枚举即可完整覆盖所有候选。相比逐位贪心，枚举不会因为先把大数字用于小时而让剩余数字无法组成合法分钟。

依次选择四个互不相同的下标 i、j、k、l，前两个组成 hour = arr[i] * 10 + arr[j]，后两个组成 minute = arr[k] * 10 + arr[l]。所有数字都非负，因此检查 hour < 24 与 minute < 60 就能确定合法性。

将合法时间转换为从零点起经过的分钟数 hour * 60 + minute，数值越大，时间越晚。小时增加一所增加的六十分钟，足以超过分钟字段之间的全部差值，因此这种比较与先比小时、再比分钟完全一致。

最佳值 best 初始化为 -1，表示还没有合法候选；合法分钟数最小为零，二者不会冲突。遍历结束后，若仍为负一则返回空串，否则用除以六十和对六十取余还原时分，再分别写出十位、个位，自然保留前导零。

同值数字可能让不同下标排列产生相同时间，但重复比较最大值不会改变答案，无须额外去重；不能因此禁止同值的另一张数字牌参与组合。

解题步骤

  1. 初始化 best = -1，四层循环分别枚举四个位置，每一层跳过前面已经选择的下标。
  2. 组成小时和分钟，只有两者都在合法范围内才继续处理。
  3. 将候选换算为总分钟数，更新最大值。
  4. 若无合法候选，返回空串；否则还原时分，并按各两位数字加中间冒号返回。

代码实现

class Solution {
    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 {
    // 负一表示尚无合法时间，零点本身是有效答案。
    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)$，输入规模固定为四，合法的下标排列最多只有 24 种，检查和格式化也都是常量操作。
  • 空间复杂度：$O(1)$，只维护下标、时分和最佳值，返回字符串长度固定为五。

关键点总结

[!green]

  • 用下标区分数字牌，每个位置恰好使用一次，允许数值相同。
  • 小规模完全枚举直接保证候选完整性，合法后再比较总分钟数。
  • 无解标记必须与合法零点区分，输出则必须保留小时和分钟的前导零。

易错点总结

[!yellow]

  • 将 best 初始化为零，会在无解时错误返回零点。
  • 只限制小时十位而不判断完整小时，会接受超出二十三的小时。
  • 只校验小时、不校验分钟，可能保留不能组成合法时刻的排列。
  • 按数值禁止重复使用，会错误丢掉输入中来自不同位置的相同数字。
  • 直接拼接未补零的时分，会使结果不满足固定的 HH:MM 格式。

相似题目

题目 难度 关联与区别
补充题 114. 六位数字组成的最晚时间 中等 从四位时分扩展到六位时分秒，仍可枚举下标排列并检查每个时间字段范围。
46. 全排列 中等 排列枚举提供所有候选，本题只保留满足小时和分钟上界的排列并取最大时间。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/13355570
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！