🚀 算法筆記：消息提及計數 (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 中。
  1. 字符串性能：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;
    }
};