LeetCode 949中等回溯 · 枚举
给定数字能组成的最大时间 图解题解
这道题到底在问什么
给定长度为 4 的数字数组 arr，用这 4 个数字各一次拼成 "HH:MM"（HH 在 00 到 23，MM 在 00 到 59），返回最大的合法时间；无解返回空串。
- 输入
- arr=[1,2,3,4]
- 输出
- "23:41"
- 输入
- arr=[5,5,5,5]
- 输出
- ""（任何排法小时都 ≥ 55）
- 输入
- arr=[0,0,0,0]
- 输出
- "00:00"
先想最直接的笨办法
核心就一句话：枚举 24 种排法，合法的留下，取最大。下面每一帧都在套它。（动画第 3 步）
最优解：一步一步想明白
- 3核心就一句话：枚举 24 种排法，合法的留下，取最大。下面每一帧都在套它。
- 4这是手里的 4 个数字。接下来把它们摆成「时-时-分-分」四个位置，逐一试遍 24 种排法。
- 5排成 12:34：小时 12 没超 23、分钟 34 没超 59，合法。它比之前见过的都大，最大时间刷新为 12:34。
- 6排成 12:43：小时 12 没超 23、分钟 43 没超 59，合法。它比之前见过的都大，最大时间刷新为 12:43。
- 7排成 13:24：小时 13 没超 23、分钟 24 没超 59，合法。它比之前见过的都大，最大时间刷新为 13:24。
- 8排成 13:42：小时 13 没超 23、分钟 42 没超 59，合法。它比之前见过的都大，最大时间刷新为 13:42。
- 9排成 14:23：小时 14 没超 23、分钟 23 没超 59，合法。它比之前见过的都大，最大时间刷新为 14:23。
- 10排成 14:32：小时 14 没超 23、分钟 32 没超 59，合法。它比之前见过的都大，最大时间刷新为 14:32。
- 11排成 21:34：小时 21 没超 23、分钟 34 没超 59，合法。它比之前见过的都大，最大时间刷新为 21:34。
- 12排成 21:43：小时 21 没超 23、分钟 43 没超 59，合法。它比之前见过的都大，最大时间刷新为 21:43。
- 13排成 23:14：小时 23 没超 23、分钟 14 没超 59，合法。它比之前见过的都大，最大时间刷新为 23:14。
- 14排成 23:41：小时 23 没超 23、分钟 41 没超 59，合法。它比之前见过的都大，最大时间刷新为 23:41。
- 15排成 24:13：小时已经到 24，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 16排成 24:31：小时是 24，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 17排成 31:24：前两位当小时是 31，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 18排成 31:42：小时凑成 31，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 19排成 32:14：小时部分是 32，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 20排成 32:41：小时已经到 32，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 21排成 34:12：小时是 34，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 22排成 34:21：前两位当小时是 34，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 23排成 41:23：小时凑成 41，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 24排成 41:32：小时部分是 41，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 25排成 42:13：小时已经到 42，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 26排成 42:31：小时是 42，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 27排成 43:12：前两位当小时是 43，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 28排成 43:21：小时凑成 43，超过 23，这种排法不是合法时间，直接淘汰。当前最大仍是 23:41。
- 2924 种排法试完，所有合法时间里 23:41 最大，它就是答案。其余排法要么超时、要么更小，都被它压下去。
⚠️ 容易写错的地方
✗ 错：只检查小时，忘了分钟也要 ≤ 59
✓ 对：小时和分钟两个条件都要满足
比如某排法凑成 06:66，分钟 66 早就越界了
✗ 错：把 24:00 当成合法
✓ 对：小时上限是 23，24 不行
24 小时制里小时取值是 00 到 23，24 点应写成次日 00:00
✗ 错：找到第一个合法就返回
✓ 对：要在所有合法时间里取最大
12:34 合法，但 23:41 更大，必须比完全部
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def largestTimeFromDigits(self, arr: List[int]) -> str:
cnt = [0] * 10
for v in arr:
cnt[v] += 1
for h in range(23, -1, -1):
for m in range(59, -1, -1):
t = [0] * 10
t[h // 10] += 1
t[h % 10] += 1
t[m // 10] += 1
t[m % 10] += 1
if cnt == t:
return f'{h:02}:{m:02}'
return ''C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
string largestTimeFromDigits(vector<int>& arr) {
int ans = -1;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 4; ++k) {
if (i != j && j != k && i != k) {
int h = arr[i] * 10 + arr[j];
int m = arr[k] * 10 + arr[6 - i - j - k];
if (h < 24 && m < 60) {
ans = max(ans, h * 60 + m);
}
}
}
}
}
if (ans < 0) return "";
int h = ans / 60, m = ans % 60;
return to_string(h / 10) + to_string(h % 10) + ":" + to_string(m / 10) + to_string(m % 10);
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public String largestTimeFromDigits(int[] arr) {
int ans = -1;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 4; ++k) {
if (i != j && j != k && i != k) {
int h = arr[i] * 10 + arr[j];
int m = arr[k] * 10 + arr[6 - i - j - k];
if (h < 24 && m < 60) {
ans = Math.max(ans, h * 60 + m);
}
}
}
}
}
return ans < 0 ? "" : String.format("%02d:%02d", ans / 60, ans % 60);
}
}复杂度
时间
O(1)
排法固定 24 种，每种校验是常数
空间
O(1)
只用几个变量记当前最大
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 给定数字能组成的最大时间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么说是常数时间复杂度？+
不管数组里是什么数字，永远只有 4 个，全排列固定是 24 种，每种排法做一次合法性校验也是常数步，所以总时间是固定的 24 量级，记作 O(1)。这是「枚举空间天然有限」的典型。
Python 参考解为什么从 23:59 倒着扫，而不枚举排列？+
换个角度：直接按时间从大到小枚举每个合法时刻 23:59、23:58、一直往下，对每个时刻看它的四位数字是不是正好等于给定的这四个数字（用计数比较）。从大到小扫，第一个能拼出来的时刻就是最大答案，省去显式生成排列。本质同样是在有限的合法时刻里挑最大，结果完全一致。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 给定数字能组成的最大时间 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。