3433. 统计用户被提及情况

🚀 算法笔记：消息提及计数 (Count Mentions)

1. 题目逻辑核心

本题是一个典型的时间序列模拟问题。其核心挑战在于处理事件的顺序性与原子状态更新。

核心解题策略

• 离线处理：预先获取所有事件并进行全局排序，构建统一的时间线。
• 优先级排序 (Tie-breaking)：在同一时刻，状态变更（下线）必须发生在行为判定（发消息）之前。

---

2. 算法实现分析

A. 事件排序逻辑 (Sorting Criteria)

排序是程序的灵魂，决定了模拟的正确性。

优先级	关键属性	排序规则	原因
1	timestamp	升序	严格遵循时间流逝顺序
2	type	OFFLINE 优先	确保 $t$ 时刻下线的人在 $t$ 时刻的 @HERE 统计中被视为“不可见”

C++

// 排序实现代码片段
sort(events.begin(), events.end(), [](const vector<string>& a, const vector<string>& b) {int timeA = stoi(a[1]), timeB = stoi(b[1]);if (timeA == timeB) return a[0] == "OFFLINE"; // OFFLINE 优先return timeA < timeB;
});

B. 状态机设计 (State Management)

与其使用 bool 记录状态并开启定时器，不如记录 “解禁时间点”。

• online_time[i]：存储用户 $i$ 重新变为 ONLINE 的时间戳。
• 状态转移逻辑：
  • 下线：online_time[userId] = timestamp + 60。
  • 判定：current_time >= online_time[userId] $\Rightarrow$ 此时用户是在线的。

C. 消息类型解析 (Dispatching)

1. ALL：全员 $O(K)$ 累加。
2. HERE：根据 online_time 过滤在线用户。
3. id<num>：精准解析。利用 token.substr(2) 剥离前缀，高效转换。

---

3. C++ 高级语法点复习

std::stringstream

它是处理变长、空格分隔字符串的利器。相比于手动 find 空格，ss >> token 更加安全且易读。

Lambda 表达式

在 sort 中直接定义闭包，避免了外部静态函数的定义，使代码更加内聚。

---

4. 复杂度深度评估

维度	复杂度 (Big O)	关键因素
时间复杂度	$O(N \log N + M \cdot K)$	$N$=事件数, $M$=消息事件数, $K$=用户总数
空间复杂度	$O(K)$	需要存储 ans 和 online_time 两个辅助数组

---

💡 潜在优化与进阶思考

1. 性能瓶颈：当 $K$（用户数）极大时，处理 ALL 消息的 $O(K)$ 循环会成为性能灾难。
   • 优化建议：引入一个全局变量 totalAllMentions。当收到 ALL 消息时只更新全局变量，最后结算时合并到每个用户的 ans 中。
2. 字符串性能：stoi 和 stringstream 涉及频繁的内存分配。
   • 优化建议：对于性能敏感场景，可改用 std::from_chars（C++17）进行极致的数值转换。

---

示例代码 (整理版)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>using namespace std;class Solution {
public:vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {// 1. 离线排序：时间优先，同时间下线优先sort(events.begin(), events.end(), [](const vector<string>& a, const vector<string>& b) {int t1 = stoi(a[1]), t2 = stoi(b[1]);return t1 == t2 ? a[0] == "OFFLINE" : t1 < t2;});vector<int> online_time(numberOfUsers, 0);vector<int> ans(numberOfUsers, 0);// 2. 模拟事件流for (const auto& e : events) {int ts = stoi(e[1]);if (e[0] == "OFFLINE") {online_time[stoi(e[2])] = ts + 60;} else {if (e[2] == "ALL") {for (int i = 0; i < numberOfUsers; ++i) ans[i]++;} else if (e[2] == "HERE") {for (int i = 0; i < numberOfUsers; ++i) {if (ts >= online_time[i]) ans[i]++;}} else {stringstream ss(e[2]);string token;while (ss >> token) ans[stoi(token.substr(2))]++;}}}return ans;}
};