681. 下一个最近的时间

题目链接（中等，会员题）

题目描述

给定一个形如 "HH:MM" 的时间字符串 time，利用该时间中已经出现过的数字，构造出下一个最近的有效时间。

数字可以重复使用任意次；
如果当天没有更晚的合法时间，答案就是第二天的最早合法时间。

数据范围：

time 是一个有效的 24 小时制时间，格式为 "HH:MM"
00 <= HH <= 23
00 <= MM <= 59

示例

示例 1：

输入： time = "19:34"
输出： "19:39"
解释： 可用数字集合为 {1, 3, 4, 9}。可以构造 19:39（5 分钟后），但不能是 19:33（那是 23 小时 59 分钟后）。

示例 2：

输入： time = "23:59"
输出： "22:22"
解释： 可用数字集合为 {2, 3, 5, 9}。当天没有更晚的合法时间，所以答案是第二天的最早合法时间 "22:22"。

核心思路

从给定时间中提取数字集合，然后用这些数字构造出「下一个比当前时间更晚的、合法的最小时间」。

如果当天存在更晚的合法时间，取其中最小的；
如果当天不存在，取第二天的最早合法时间（即所有合法时间中的最小值）。

三种解法：

暴力枚举：从当前时间往后逐分钟模拟，最多 1440 次，检查每一位数字是否都在集合中；
DFS 回溯：枚举所有 4 位数字组合，过滤合法时间，找严格大于当前时间的最小值；
贪心模拟：从最低位到最高位依次尝试替换为更大的数字，最坏情况全部重置为最小值。

方法一：暴力枚举（模拟时钟走时）✅ 推荐

思路及解法

一天只有 1440 分钟。从当前时间的下一分钟开始，最多遍历 1440 次，就一定可以覆盖所有可能的时间点。

对于每一个遍历到的时间，检查其四位数字是否都在原始时间的数字集合中出现过。第一个符合条件的时间就是答案。

为什么最多 1440 次：

一天共 24 × 60 = 1440 分钟；
若当天没有合法时间，遍历 1440 次后会回到当前时间；
由于第二天必然存在至少一个合法时间（四位数字全用最小数字构造），所以最多 1440 次一定能找到答案。

代码

class Solution:
    def nextClosestTime(self, time: str) -> str:
        # 1. 提取原始时间中的数字集合
        digits = set(time)
        digits.discard(':')

        # 2. 将当前时间转换为分钟数
        h, m = map(int, time.split(':'))
        cur = h * 60 + m

        # 3. 最多遍历 1440 分钟
        for i in range(1, 1441):
            nxt = (cur + i) % 1440
            hh, mm = divmod(nxt, 60)
            t = f"{hh:02d}:{mm:02d}"
            # 检查是否所有数字都在 digits 中
            if all(ch in digits for ch in t if ch != ':'):
                return t

复杂度分析

时间复杂度：$O(1)$。最多 1440 次迭代，每次检查常数个字符。
空间复杂度：$O(1)$。只使用常数大小的集合。

方法二：DFS 回溯（枚举所有组合）

思路及解法

从原始时间中提取数字集合，然后 DFS 枚举所有 4 位组合，过滤出合法的时间（小时 00-23，分钟 00-59），最后：

找到严格大于当前时间的最小值作为答案；
如果不存在，则返回所有合法时间中的最小值（即第二天的答案）。

为什么 DFS 可行：数字集合最多 4 个不同数字，4 位组合最多 $4^4 = 256$ 种，规模极小。

代码

class Solution:
    def nextClosestTime(self, time: str) -> str:
        digits = list(set(time.replace(':', '')))
        cur_h, cur_m = map(int, time.split(':'))
        cur_total = cur_h * 60 + cur_m

        valid_times = []

        def dfs(path):
            if len(path) == 4:
                h = int(path[0]) * 10 + int(path[1])
                m = int(path[2]) * 10 + int(path[3])
                if h < 24 and m < 60:
                    valid_times.append((h, m))
                return
            for d in digits:
                dfs(path + d)

        dfs('')

        # 找严格大于当前时间的最小值
        best = None
        best_total = float('inf')
        for h, m in valid_times:
            total = h * 60 + m
            if total > cur_total and total < best_total:
                best_total = total
                best = (h, m)

        # 没有更大的，取全局最小值（第二天）
        if best is None:
            best = min(valid_times, key=lambda x: x[0] * 60 + x[1])

        return f"{best[0]:02d}:{best[1]:02d}"

复杂度分析

时间复杂度：$O(4^4) = O(1)$，最多 256 种组合。
空间复杂度：$O(4^4)$，存储所有合法时间组合。

方法三：贪心模拟（从低位到高位尝试替换）

思路及解法

从最低位（分钟个位）开始，尝试替换成数字集合中比当前位大的最小数字。如果替换后能构成合法时间，立即返回；否则将该位替换为集合中的最小值，继续处理更高位。

如果所有位都无法替换成更大的合法值，说明答案在第二天，此时所有位都已变成各自的最小值。

为什么从低位到高位：

要让「下一个时间」尽可能近，应该优先修改低位的数字；
只有低位无法修改时，才动高位。

边界处理：

替换分钟个位：分钟值必须 < 60；
替换分钟十位：分钟值必须 < 60，且分钟个位重置为最小值；
替换小时个位：小时值必须 < 24，且分钟位重置为最小值；
替换小时十位：小时值必须 < 24，且小时个位、分钟位重置为最小值。

代码

class Solution:
    def nextClosestTime(self, time: str) -> str:
        digits = sorted(set(time.replace(':', '')))
        res = list(time)

        # 从最低位到最高位尝试替换
        for i in [4, 3, 1, 0]:
            pos = digits.index(res[i])
            if pos + 1 < len(digits):
                next_digit = digits[pos + 1]
                candidate = res[:]
                candidate[i] = next_digit

                if i == 4:                           # 分钟个位
                    h = int(''.join(candidate[:2]))
                    m = int(''.join(candidate[3:]))
                    if h < 24 and m < 60:
                        return ''.join(candidate)
                elif i == 3:                         # 分钟十位
                    m = int(''.join(candidate[3:]))
                    if m < 60:
                        candidate[4] = digits[0]
                        return ''.join(candidate)
                elif i == 1:                         # 小时个位
                    h = int(''.join(candidate[:2]))
                    if h < 24:
                        candidate[3] = candidate[4] = digits[0]
                        return ''.join(candidate)
                elif i == 0:                         # 小时十位
                    h = int(''.join(candidate[:2]))
                    if h < 24:
                        candidate[1] = digits[0]
                        candidate[3] = candidate[4] = digits[0]
                        return ''.join(candidate)

            # 无法替换为更大的合法值，重置为最小值
            res[i] = digits[0]

        return ''.join(res)

复杂度分析

时间复杂度：$O(1)$，只检查固定的 4 个位置。
空间复杂度：$O(1)$。

三种方法对比

方法	时间	空间	特点
暴力枚举	$O(1)$	$O(1)$	代码最短，最不容易出错，面试首选
DFS 回溯	$O(1)$	$O(1)$	思路直观，但需额外排序找最小值
贪心模拟	$O(1)$	$O(1)$	最高效，但边界条件多，容易写错

关键细节

1. 数字集合的提取

digits = set(time.replace(':', ''))

把冒号去掉，剩下的就是 4 个数字字符。用集合去重，因为同一个数字可以重复使用。

2. 暴力枚举为什么最多 1440 次

一天有 1440 分钟，从当前时间的下一分钟开始循环，(cur + i) % 1440 会遍历所有时间点。若当天没有合法时间，走完 1440 次后会回到当前时间，此时第二天的最早合法时间一定已经被遍历过。

3. 格式化输出

t = f"{hh:02d}:{mm:02d}"

02d 保证小时和分钟都是两位数，不足两位补前导零。

4. DFS 中「严格大于」的含义

题目要求的是「下一个」，所以必须是 total > cur_total，不能等于。

5. 贪心法的重置逻辑

当某一位无法替换成更大的合法数字时，把它重置为数字集合中的最小值。这样后续更高位替换后，低位的数字尽可能小，保证结果最小。

举例：time = "23:59"，digits = [2, 3, 5, 9]

i=4（分钟个位）：'9' 已是最大，重置为 '2'；
i=3（分钟十位）：'5' 替换为 '9'，但 "99" 分钟非法，重置为 '2'；
i=1（小时个位）：'3' 替换为 '5'，但 "25" 小时非法，重置为 '2'；
i=0（小时十位）：'2' 替换为 '3'，但 "32" 小时非法，重置为 '2'。

最终 res = "22:22"。

6. 为什么 DFS 不需要考虑「第二天」

DFS 枚举了所有合法时间，包括比当前时间小的。如果当天没有更大的，就取全局最小值，正好是第二天的答案。

总结

问题本质：用给定数字构造「下一个最近的有效时间」；
暴力枚举：
- 从当前时间往后逐分钟模拟，最多 1440 次；
- 检查四位数字是否都在集合中；
- 代码最短，最稳妥；
DFS 回溯：
- 枚举所有 4 位组合，筛选合法时间；
- 找严格大于当前时间的最小值，找不到则取全局最小；
贪心模拟：
- 从低位到高位尝试替换为更大的数字；
- 无法替换则重置为最小值；
- 效率最高，但边界多；
通用套路：「时间类枚举」→ 暴力枚举 1440 分钟最省心，因为常数极小、逻辑最清晰。

681. 下一个最近的时间

681. 下一个最近的时间

题目描述

示例

核心思路

方法一：暴力枚举（模拟时钟走时）✅ 推荐

思路及解法

代码

复杂度分析

方法二：DFS 回溯（枚举所有组合）

思路及解法

代码

复杂度分析

方法三：贪心模拟（从低位到高位尝试替换）

思路及解法

代码

复杂度分析

三种方法对比

关键细节

1. 数字集合的提取

2. 暴力枚举为什么最多 1440 次

3. 格式化输出

4. DFS 中「严格大于」的含义

5. 贪心法的重置逻辑

6. 为什么 DFS 不需要考虑「第二天」

总结

相关题目