LeetCode 359. 日志速率限制器
题目描述
题意分析
设计一个日志判断器，接收时间戳与完整消息，返回这次是否允许打印。同一条消息成功打印后，接下来的十秒内再次请求都应被拒绝，恰好相隔十秒可以再次打印。
时间戳按非递减顺序到来，不同消息独立限速。被拒绝的请求没有真正打印，不能以它的时间重新开始计时；函数只返回是否获准，不需要执行实际打印。
解法：记录每条消息上次获准的时间
核心思路
[!blue]
只需要知道同一消息最后一次成功打印的时间，就能判断当前请求。更早的成功记录都不比最新记录更接近当前时间；所有失败请求又不会产生新的限制，所以不必保存完整历史。
用哈希表
last以完整消息为键，记录上次获准时间。若没有这个键，说明消息尚未成功打印，直接允许；否则比较timestamp - previous与十。间隔不足十时返回
false，保持原记录不变。间隔达到十时返回true，并用当前时间替换记录，新的冷却区间从这次成功开始。每轮结束后，表中每条消息的值都仍是它最近一次真正获准的时间，这个状态足以决定下一次同消息请求。相同时间的重复消息会被拒绝，但其他消息不会受它影响。
解题步骤
- 初始化空哈希表，实例持续保存不同调用之间的状态。
- 查询当前完整消息的上次获准时间。
- 已有记录且间隔不足十秒时，直接拒绝，不修改表。
- 其他情况记录当前时间，并返回允许。
代码实现
class Logger {
private final Map<String, Integer> last = new HashMap<>();
public boolean shouldPrintMessage(int timestamp, String message) {
Integer previous = last.get(message);
if (previous != null && timestamp - previous < 10) {
return false;
}
last.put(message, timestamp);
return true;
}
}
type Logger struct {
last map[string]int
}
func Constructor() Logger {
return Logger{last: map[string]int{}}
}
func (l *Logger) ShouldPrintMessage(timestamp int, message string) bool {
previous, exists := l.last[message]
if exists && timestamp-previous < 10 {
return false
}
l.last[message] = timestamp
return true
}
复杂度分析
- 时间复杂度：一次请求平均做常数次哈希操作；计入消息字符串哈希和比较，期望为 $O(L)$，其中 $L$ 为消息长度。
- 空间复杂度：$O(U)$ 个字典条目，其中 $U$ 为成功出现过的不同消息数，另需保存对应消息文本。当前实现不清理旧键，空间随不同消息数量增长。
关键点总结
[!green]
- 限速基准是上次获准时间，失败请求不改变状态。
- 相同消息独立计时，只需一条最新成功记录。
- 是否存在键与时间值本身分开判断，时间戳零也是正常值。
易错点总结
[!yellow]
- 拒绝时也更新时间，会让连续重试不断推迟允许时刻，改变题目规则。
- 把间隔条件写成小于或等于十，会误拒绝恰好到期的请求。
- 用记录值等于零表示不存在，会混淆时间戳零处的真实成功记录。
- 所有消息共用一个最后时间，会错误地让不同消息互相限制。
- 每次调用重新创建表会丢失历史，表应属于持续使用的实例。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 933. 最近的请求次数 | 简单 | 都依据时间窗口处理请求；本题按消息独立保留上次成功时间，不需要保留全部请求。 |
| 362. 敲击计数器 | 中等 | 对照统计全部命中次数的时间队列；限速判断与窗口计数需要保存的信息不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！