---

0681. 最近时刻

• 标签：哈希表、字符串、回溯、枚举
• 难度：中等

题目链接

• 0681. 最近时刻 - 力扣

题目大意

描述：

给定一个形如 "HH:MM" 表示的时刻 time，利用当前出现过的数字构造下一个距离当前时间最近的时刻。每个出现数字都可以被无限次使用。

你可以认为给定的字符串一定是合法的。例如，"01:34" 和 "12:09" 是合法的，"1:34" 和 "12:9" 是不合法的。

要求：

返回下一个最近的时刻。

说明：

• $time.length == 5$。
• $time$ 为有效时间，格式为 "HH:MM"。
• $0 \le HH < 24$。
• $0 \le MM < 60$。

示例：

• 示例 1：

输入："19:34"
输出："19:39"
解释：利用数字 1, 9, 3, 4 构造出来的最近时刻是 19:39，是 5 分钟之后。
结果不是 19:33 因为这个时刻是 23 小时 59 分钟之后。

• 示例 2：

输入："23:59"
输出："22:22"
解释：利用数字 2, 3, 5, 9 构造出来的最近时刻是 22:22。答案一定是第二天的某一时刻，所以选择可表示的最小时刻。

解题思路

思路 1：枚举 + 模拟

思路 1：算法描述

给定当前时间，需要找到下一个最近的时刻，且只能使用当前时间中出现的数字。

核心思路：

• 从当前时间开始，逐分钟递增，检查每个时刻是否只包含当前时间中的数字。
• 最多检查 $24 \times 60 = 1440$ 个时刻（一天的分钟数）。

算法步骤：

1. 提取当前时间中出现的所有数字，存入集合。
2. 将时间转换为分钟数。
3. 从下一分钟开始，逐分钟递增：
   • 将分钟数转换为时间格式。
   • 检查时间中的所有数字是否都在集合中。
   • 如果是，返回该时间。
4. 循环最多 $1440$ 次（一天）。

思路 1：代码

class Solution:
    def nextClosestTime(self, time: str) -> str:
        # 提取当前时间中的数字
        digits = set(time.replace(':', ''))
        
        # 将时间转换为分钟数
        hour, minute = map(int, time.split(':'))
        current_minutes = hour * 60 + minute
        
        # 从下一分钟开始查找
        for i in range(1, 24 * 60 + 1):
            next_minutes = (current_minutes + i) % (24 * 60)
            next_hour = next_minutes // 60
            next_minute = next_minutes % 60
            
            # 格式化时间
            next_time = f"{next_hour:02d}:{next_minute:02d}"
            
            # 检查是否只包含原有数字
            if all(d in digits for d in next_time.replace(':', '')):
                return next_time
        
        return time

思路 1：复杂度分析

• 时间复杂度：$O(1)$，最多检查 $1440$ 个时刻，每次检查需要常数时间。
• 空间复杂度：$O(1)$，只使用了常数额外空间。