用户活跃分钟数统计系统

题目

用户活跃分钟数统计系统

信息

• 类型：问答
• 难度：⭐⭐

考点

哈希表设计,滑动窗口,时间序列处理

快速回答

设计一个统计用户活跃分钟数的系统，需要高效处理登录事件和查询请求：

• 使用全局变量记录系统当前时间
• 为每个用户维护一个双端队列（存储登录分钟）和一个哈希集合（快速判重）
• 登录时更新全局时间，将新分钟加入队列和集合（需去重）
• 移除窗口外过期数据：队列头部小于 currentMinute - k + 1 的分钟
• 查询时同样移除过期数据后返回队列长度

问题分析

需要设计一个系统统计用户在最近 k 分钟内的活跃分钟数（同一分钟多次登录只计一次）。核心挑战：

1. 高效处理严格递增的时间序列
2. 动态维护滑动时间窗口
3. 快速去重和过期数据清理
4. 支持高频登录和查询操作

设计思路

采用分层数据结构：

• 全局时间跟踪：记录最后登录时间作为系统当前时间
• 用户级存储：哈希表映射用户ID到数据结构（双端队列+哈希集合）
  • 双端队列：按时间顺序存储不同的登录分钟
  • 哈希集合：快速判断分钟是否已存在（O(1)复杂度）

核心操作

登录操作 login(userId, currentMinute)

1. 更新全局时间为 currentMinute
2. 若用户不存在，初始化队列和集合
3. 若分钟不在集合中：
   • 加入集合
   • 加入队列尾部
4. 计算窗口下限：low = currentMinute - k + 1
5. 移除队列头部所有小于 low 的过期分钟（同步移除集合中元素）

查询操作 getActiveMinutes(userId)

1. 若用户不存在，返回 0
2. 使用全局时间计算当前窗口下限
3. 移除该用户所有过期分钟（同登录操作）
4. 返回队列长度（即活跃分钟数）

代码示例（Python）

from collections import deque

class ActiveMinutes:
    def __init__(self, k: int):
        self.k = k
        self.global_minute = -1  # 系统当前时间
        self.user_data = {}      # userId: {'queue': deque, 'set': set}

    def login(self, userId: int, currentMinute: int) -> None:
        # 更新系统时间
        self.global_minute = currentMinute

        # 初始化用户数据结构
        if userId not in self.user_data:
            self.user_data[userId] = {'queue': deque(), 'set': set()}

        user = self.user_data[userId]

        # 分钟去重检查
        if currentMinute in user['set']:
            return

        # 记录新分钟
        user['set'].add(currentMinute)
        user['queue'].append(currentMinute)

        # 移除过期数据
        self._remove_expired(user)

    def getActiveMinutes(self, userId: int) -> int:
        if userId not in self.user_data:
            return 0

        user = self.user_data[userId]
        self._remove_expired(user)
        return len(user['queue'])

    def _remove_expired(self, user: dict):
        low_bound = self.global_minute - self.k + 1
        queue = user['queue']
        minute_set = user['set']

        # 移除队列头部过期分钟
        while queue and queue[0] < low_bound:
            expired_minute = queue.popleft()
            minute_set.remove(expired_minute)

时间复杂度分析

最佳实践

• 惰性删除：在登录和查询时执行过期清理，避免定时任务开销
• 双数据结构：队列维护时间顺序，集合实现快速去重
• 全局时间：以最后一次登录时间作为系统基准时间
• 边界处理：未登录用户直接返回0，避免空指针

常见错误

• 未处理重复分钟：导致同一分钟被多次计数
• 未及时清理过期数据：查询结果包含历史数据
• 错误的时间窗口计算：窗口应为 [currentMinute-k+1, currentMinute]
• 查询时未更新窗口：需使用最新全局时间重新计算
• 数据结构选择不当：仅用集合无法维护时间顺序，仅用队列无法快速去重

扩展知识

• 时间窗口优化：对于超大k值，可考虑时间分片（Time Bucketing）
• 分布式场景：使用一致性哈希分配用户数据到不同节点
• 数据持久化：Redis的Sorted Set可天然支持类似功能（ZADD/ZREMRANGEBYSCORE）
• 近似计数：海量用户场景可用HyperLogLog牺牲精度换空间
• 关联算法：滑动窗口最大值问题（Monotonic Queue），流处理中的Time-Windowed Aggregation