假设有一个用户行为日志，记录了用户ID和操作时间戳（如'2023-10-01 10:00'），时间窗口为最近7天。请设计一个算法，高效计算每个用户的活跃度（即7天内至少有一次登录行为的用户），并找出活跃用户Top N（比如Top 1000）。请说明时间复杂度和空间复杂度。
答案
1) 【一句话结论】
采用滑动窗口（双端队列维护时间戳）结合哈希表统计活跃用户，再用最大堆维护Top N，时间复杂度O(N + K log K)，空间复杂度O(N+K)，适用于大数据量或流式数据实时更新场景。
2) 【原理/概念讲解】
老师：“要高效计算7天活跃用户并取Top N，核心是处理时间窗口的动态变化。首先，时间窗口是最近7天，需维护一个大小为7天的滑动窗口。用**双端队列（deque）存储每个用户最近一次登录的时间戳，当新记录时间超过窗口（即超过当前时间-7天）时，移除队列头部（最早的时间戳），并从哈希表删除该用户，避免旧数据残留。哈希表用于记录每个用户是否在窗口内登录过（只要有一个记录就算1次，值设为1即可）。对于Top N，用最大堆（优先队列）**维护，每次新用户进入窗口时，若堆大小小于N则直接加入；若等于N且新用户时间戳比堆顶（当前Top N中最小的时间戳）大，则替换堆顶。这样能实时维护Top N。类比的话，双端队列就像一个滑动的时间窗口，只保留最近7天的记录，哈希表快速判断用户是否活跃，最大堆则高效维护Top N。”
3) 【对比与适用场景】
| 方法 | 定义 | 特性 | 使用场景 | 注意点 |
|---|---|---|---|---|
| 滑动窗口+哈希表+堆（流式） | 维护时间戳双端队列，增量更新哈希表，用最大堆维护Top N | 时间复杂度O(N + K log K)，空间O(N+K)，支持实时更新 | 大数据量、流式数据、需要动态维护Top N | 需要额外数据结构（双端队列、堆），实现复杂度较高 |
| 全量扫描+哈希表+排序（静态） | 一次性过滤所有日志，统计活跃后排序取Top N | 时间复杂度O(N + M log M)，空间O(M) | 数据量小、静态数据、不需要实时更新 | 排序耗时，若M远小于N，效率尚可 |
| 哈希表+排序（简单过滤） | 过滤时间窗口后直接排序用户ID取Top N | 时间复杂度O(N + M log M)，空间O(M) | 小规模数据，简单场景 | 未考虑实时更新，数据量大时效率低 |
4) 【示例】
假设日志数据（用户ID, 时间戳，单位ms）：
- user1: 1696121600000 (2023-10-01 10:00)
- user2: 1695235200000 (2023-09-28 09:00)
- user3: 1696232000000 (2023-10-05 11:00)
- user1: 1696257600000 (2023-10-06 12:00)
- user4: 1696263600000 (2023-10-07 13:00)
当前时间now=1696344000000 (2023-10-08 10:00)，窗口为7天（1696264000000 - 1696344000000）。
过滤后有效记录：user1, user3, user1, user4。
初始化双端队列dq = []，哈希表active={}; 最大堆topk=[]（存储(时间戳, 用户ID)，堆顶为最大时间戳）。
遍历记录时： - user1的1696121600000在窗口内，dq.append(1696121600000)，active[1696121600000]=user1。
- user2的1695235200000<窗口起始时间，忽略。
- user3的1696232000000在窗口内，dq.append(1696232000000)，active[1696232000000]=user3。
- user1的1696257600000在窗口内，dq.append(1696257600000)，active更新。
- user4的1696263600000在窗口内，dq.append(1696263600000)，active[1696263600000]=user4。
- 维护Top N：将active的3个用户加入堆，若堆大小<1000则push，否则替换堆顶。最终堆中是Top 1000用户（按时间戳降序）。
伪代码（简化）：
import heapq
from collections import deque
def get_top_active_users(logs, now, N):
window_start = now - 7 * 24 * 60 * 60 * 1000 # 7天毫秒数
dq = deque() # 存储时间戳
active = {} # 用户是否活跃
topk = [] # 最大堆，存储 (时间戳, 用户ID)
for user, ts in logs:
if ts < window_start:
continue
# 移除超出窗口的旧时间戳
while dq and dq[0] < ts - window_start:
old_ts = dq.popleft()
if active.get(old_ts) is not None:
del active[old_ts]
dq.append(ts)
active[ts] = user
# 更新Top N
if len(topk) < N:
heapq.heappush(topk, (ts, user))
else:
if ts > topk[0][0]:
heapq.heapreplace(topk, (ts, user))
top_users = [user for _, user in sorted(topk, reverse=True)]
return top_users
5) 【面试口播版答案】
“首先，这个问题要计算最近7天活跃用户并找出Top N。核心思路是采用滑动窗口结合哈希表和最大堆，实现高效动态更新。步骤是：1. 定义时间窗口（当前时间减7天）；2. 用双端队列维护每个用户最近一次登录的时间戳，当新记录时间超过窗口时，移除队列头部（旧时间戳），并从哈希表删除该用户，避免旧数据干扰；3. 用哈希表记录每个用户是否在窗口内登录过（只要有一个记录就算1次）；4. 用最大堆维护Top N，每次新用户进入窗口时，若堆大小小于N则加入，若等于N且新用户时间戳比堆顶大，则替换堆顶，这样能实时保持Top N。时间复杂度方面，遍历日志是O(N)，维护双端队列和堆是O(1)每次，总时间O(N + K log K)，空间复杂度是O(N+K)，其中N是日志数量，K是Top N数量。这种方法适用于大数据量或流式数据，能高效处理实时更新。”
6) 【追问清单】
- 数据量很大时如何优化？
回答要点：采用流式处理，维护滑动窗口（双端队列），增量更新哈希表和堆，避免全量扫描，提升效率。 - 时间窗口动态调整（比如从7天改为5天）时怎么办？
回答要点：调整窗口大小，重新计算窗口起始时间，更新双端队列的移除条件（队列长度或时间戳比较），并重新维护哈希表和堆。 - 需要实时计算Top N时如何处理？
回答要点：用最大堆（优先队列），每次新记录到来时更新堆，保持堆大小为N，实时返回Top N，无需等待所有数据。 - 用户有多个操作（如登录、退出），是否需要考虑？
回答要点：只要登录行为算一次，退出不算，所以只要时间在窗口内登录过就算活跃，操作类型不影响统计。 - 时间格式转换是否会影响效率？
回答要点：统一转换为时间戳（整数或浮点数），避免字符串比较的额外开销，提升比较效率。
7) 【常见坑/雷区】
- 忽略时间窗口过滤：直接统计所有用户，导致结果包含历史数据，错误。
- 混淆活跃用户定义：误认为需要登录次数大于1，导致统计错误（题目中是“至少一次”）。
- 时间复杂度分析错误：未考虑滑动窗口的维护和堆的更新，比如直接排序所有用户而非活跃用户。
- 空间复杂度遗漏：未说明双端队列和堆需要额外空间，导致空间复杂度分析不完整。
- 未处理数据量大的情况：未提及流式处理或滑动窗口机制，显得方案不实用，无法应对实时数据。