注意输入的 $\textit{events}$ 不保证是按时间顺序发生的，需要先排序。

按照时间戳 $\textit{timestamp}$ 从小到大排序，时间戳相同的，离线事件排在前面，因为题目要求「状态变更在所有相同时间发生的消息事件之前处理」。

然后模拟：

• 离线事件：用一个数组 $\textit{onlineT}$ 记录用户下次在线的时间戳（$60$ 秒后）。如果 $\textit{onlineT}[i]\le$ 当前时间戳，则表示用户 $i$ 已在线。
• 消息事件：把相应用户的提及次数加一。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
        # 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面
        events.sort(key=lambda e: (int(e[1]), e[0][2]))

        ans = [0] * numberOfUsers
        online_t = [0] * numberOfUsers
        for type_, timestamp, mention in events:
            cur_t = int(timestamp)  # 当前时间
            if type_[0] == 'O':  # 离线
                online_t[int(mention)] = cur_t + 60  # 下次在线时间
            elif mention[0] == 'A':  # @所有人
                for i in range(numberOfUsers):
                    ans[i] += 1
            elif mention[0] == 'H':  # @所有在线用户
                for i, t in enumerate(online_t):
                    if t <= cur_t:  # 在线
                        ans[i] += 1
            else:  # @id
                for s in mention.split():
                    ans[int(s[2:])] += 1
        return ans

###java

class Solution {
    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
        // 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面
        events.sort((a, b) -> {
            int ta = Integer.parseInt(a.get(1));
            int tb = Integer.parseInt(b.get(1));
            return ta != tb ? ta - tb : b.get(0).charAt(0) - a.get(0).charAt(0);
        });

        int[] ans = new int[numberOfUsers];
        int[] onlineT = new int[numberOfUsers];
        for (List<String> e : events) {
            int curT = Integer.parseInt(e.get(1)); // 当前时间
            String mention = e.get(2);
            if (e.get(0).charAt(0) == 'O') { // 离线
                onlineT[Integer.parseInt(mention)] = curT + 60; // 下次在线时间
            } else if (mention.charAt(0) == 'A') { // @所有人
                for (int i = 0; i < numberOfUsers; i++) {
                    ans[i]++;
                }
            } else if (mention.charAt(0) == 'H') { // @所有在线用户
                for (int i = 0; i < numberOfUsers; i++) {
                    if (onlineT[i] <= curT) { // 在线
                        ans[i]++;
                    }
                }
            } else { // @id
                for (String s : mention.split(" ")) {
                    int i = Integer.parseInt(s.substring(2));
                    ans[i]++;
                }
            }
        }
        return ans;
    }
}

###cpp

#include<ranges>
class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        // 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面
        ranges::sort(events, {}, [](auto& e) {
            return pair(stoi(e[1]), e[0][2]);
        });

        vector<int> ans(numberOfUsers);
        vector<int> online_t(numberOfUsers);
        for (auto& e : events) {
            int cur_t = stoi(e[1]); // 当前时间
            string& mention = e[2];
            if (e[0][0] == 'O') { // 离线
                online_t[stoi(mention)] = cur_t + 60; // 下次在线时间
            } else if (mention[0] == 'A') { // @所有人
                for (int& v : ans) {
                    v++;
                }
            } else if (mention[0] == 'H') { // @所有在线用户
                for (int i = 0; i < numberOfUsers; i++) {
                    if (online_t[i] <= cur_t) { // 在线
                        ans[i]++;
                    }
                }
            } else { // @id
                for (const auto& part : mention | ranges::views::split(' ')) {
                    string s(part.begin() + 2, part.end());
                    ans[stoi(s)]++;
                }
            }
        }
        return ans;
    }
};

###c

// 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面
int cmp(const void* p, const void* q) {
    char** a = *(char***)p;
    char** b = *(char***)q;
    int ta = atoi(a[1]);
    int tb = atoi(b[1]);
    return ta != tb ? ta - tb : b[0][0] - a[0][0];
}

int* countMentions(int numberOfUsers, char*** events, int eventsSize, int* eventsColSize, int* returnSize) {
    qsort(events, eventsSize, sizeof(char**), cmp);

    *returnSize = numberOfUsers;
    int* ans = calloc(numberOfUsers, sizeof(int));
    int* online_t = calloc(numberOfUsers, sizeof(int));

    for (int i = 0; i < eventsSize; i++) {
        char** e = events[i];
        int cur_t = atoi(e[1]); // 当前时间
        char* mention = e[2];

        if (e[0][0] == 'O') { // 离线
            online_t[atoi(mention)] = cur_t + 60; // 下次在线时间
        } else if (mention[0] == 'A') { // @所有人
            for (int i = 0; i < numberOfUsers; i++) {
                ans[i]++;
            }
        } else if (mention[0] == 'H') { // @所有在线用户
            for (int i = 0; i < numberOfUsers; i++) {
                if (online_t[i] <= cur_t) { // 在线
                    ans[i]++;
                }
            }
        } else { // @id
            // 注：如果不想修改输入的话，可以先复制一份 mention
            for (char* tok = strtok(mention, " "); tok; tok = strtok(NULL, " ")) {
                ans[atoi(tok + 2)]++;
            }
        }
    }

    free(online_t);
    return ans;
}

###go

func countMentions(numberOfUsers int, events [][]string) []int {
// 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面
slices.SortFunc(events, func(a, b []string) int {
ta, _ := strconv.Atoi(a[1])
tb, _ := strconv.Atoi(b[1])
return cmp.Or(ta-tb, int(b[0][0])-int(a[0][0]))
})

ans := make([]int, numberOfUsers)
onlineT := make([]int, numberOfUsers)
for _, e := range events {
curT, _ := strconv.Atoi(e[1]) // 当前时间
mention := e[2]
if e[0][0] == 'O' { // 离线
i, _ := strconv.Atoi(mention)
onlineT[i] = curT + 60 // 下次在线时间
} else if mention[0] == 'A' { // @所有人
for i := range ans {
ans[i]++
}
} else if mention[0] == 'H' { // @所有在线用户
for i, t := range onlineT {
if t <= curT { // 在线
ans[i]++
}
}
} else { // @id
for _, s := range strings.Split(mention, " ") {
i, _ := strconv.Atoi(s[2:])
ans[i]++
}
}
}
return ans
}

###js

var countMentions = function(numberOfUsers, events) {
    // 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面
    events.sort((a, b) => parseInt(a[1]) - parseInt(b[1]) || b[0][0].charCodeAt(0) - a[0][0].charCodeAt(0));

    const ans = Array(numberOfUsers).fill(0);
    const onlineT = Array(numberOfUsers).fill(0);
    for (const [type, timestamp, mention] of events) {
        const curT = parseInt(timestamp); // 当前时间
        if (type[0] === 'O') { // 离线
            onlineT[parseInt(mention)] = curT + 60; // 下次在线时间
        } else if (mention[0] === 'A') { // @所有人
            for (let i = 0; i < numberOfUsers; i++) {
                ans[i]++;
            }
        } else if (mention[0] === 'H') { // @所有在线用户
            for (let i = 0; i < numberOfUsers; i++) {
                if (onlineT[i] <= curT) { // 在线
                    ans[i]++;
                }
            }
        } else { // @id
            for (const s of mention.split(" ")) {
                ans[parseInt(s.slice(2))] += 1;
            }
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn count_mentions(number_of_users: i32, mut events: Vec<Vec<String>>) -> Vec<i32> {
        // 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面
        events.sort_unstable_by_key(|e| (e[1].parse::<i32>().unwrap(), e[0].as_bytes()[2]));

        let n = number_of_users as usize;
        let mut ans = vec![0; n];
        let mut online_t = vec![0; n];
        for e in events {
            let cur_t = e[1].parse().unwrap(); // 当前时间
            let mention = &e[2];
            if e[0].as_bytes()[0] == b'O' { // 离线
                online_t[mention.parse::<usize>().unwrap()] = cur_t + 60; // 下次在线时间
            } else if mention.as_bytes()[0] == b'A' { // @所有人
                for cnt in ans.iter_mut() {
                    *cnt += 1;
                }
            } else if mention.as_bytes()[0] == b'H' { // @所有在线用户
                for (&t, cnt) in online_t.iter().zip(ans.iter_mut()) {
                    if t <= cur_t { // 在线
                        *cnt += 1;
                    }
                }
            } else { // @id
                for s in mention.split(' ') {
                    ans[s[2..].parse::<usize>().unwrap()] += 1;
                }
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn + m\log m\log U + L)$，其中 $m$ 是 $\textit{events}$ 的长度，$n$ 是 $\textit{numberOfUsers}$，$U\le 10^5$ 是时间戳的最大值，$L$ 是所有 mentions_string 的长度之和。排序需要 $\mathcal{O}(m\log m)$ 次比较，每次比较需要 $\mathcal{O}(\log U)$ 的时间把长为 $\mathcal{O}(\log U)$ 的字符串时间戳转成整数。注：如果预处理这个转换，可以把排序的过程优化至 $\mathcal{O}(m\log m)$。
• 空间复杂度：$\mathcal{O}(n)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

分析

如果一个点在同一行的最左边，那么它左边没有点；如果一个点在同一行的最右边，那么它右边没有点。

如果一个点在同一列的最上边，那么它上边没有点；如果一个点在同一列的最下边，那么它下边没有点。

反之，如果一个点不在同一行的最左边也不在最右边，那么这个点左右都有点；如果一个点不在同一列的最上边也不在最下边，那么这个点上下都有点。

算法

记录同一行的最小横坐标和最大横坐标，同一列的最小纵坐标和最大纵坐标。

对于每个建筑 $(x,y)$，如果 $x$ 在这一行的最小值和最大值之间（不能相等），$y$ 在这一列的最小值和最大值之间（不能相等），那么答案加一。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        row_min = [n + 1] * (n + 1)
        row_max = [0] * (n + 1)
        col_min = [n + 1] * (n + 1)
        col_max = [0] * (n + 1)

        for x, y in buildings:
            # 手写 min max 更快
            if x < row_min[y]: row_min[y] = x
            if x > row_max[y]: row_max[y] = x
            if y < col_min[x]: col_min[x] = y
            if y > col_max[x]: col_max[x] = y

        ans = 0
        for x, y in buildings:
            if row_min[y] < x < row_max[y] and col_min[x] < y < col_max[x]:
                ans += 1
        return ans

###java

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        int[] rowMin = new int[n + 1];
        int[] rowMax = new int[n + 1];
        int[] colMin = new int[n + 1];
        int[] colMax = new int[n + 1];
        Arrays.fill(rowMin, n + 1);
        Arrays.fill(colMin, n + 1);

        for (int[] p : buildings) {
            int x = p[0], y = p[1];
            rowMin[y] = Math.min(rowMin[y], x);
            rowMax[y] = Math.max(rowMax[y], x);
            colMin[x] = Math.min(colMin[x], y);
            colMax[x] = Math.max(colMax[x], y);
        }

        int ans = 0;
        for (int[] p : buildings) {
            int x = p[0], y = p[1];
            if (rowMin[y] < x && x < rowMax[y] && colMin[x] < y && y < colMax[x]) {
                ans++;
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        vector<int> row_min(n + 1, INT_MAX), row_max(n + 1);
        vector<int> col_min(n + 1, INT_MAX), col_max(n + 1);
        for (auto& p : buildings) {
            int x = p[0], y = p[1];
            row_min[y] = min(row_min[y], x);
            row_max[y] = max(row_max[y], x);
            col_min[x] = min(col_min[x], y);
            col_max[x] = max(col_max[x], y);
        }

        int ans = 0;
        for (auto& p : buildings) {
            int x = p[0], y = p[1];
            if (row_min[y] < x && x < row_max[y] && col_min[x] < y && y < col_max[x]) {
                ans++;
            }
        }
        return ans;
    }
};

###go

func countCoveredBuildings(n int, buildings [][]int) (ans int) {
type pair struct{ min, max int }
row := make([]pair, n+1)
col := make([]pair, n+1)
for i := 1; i <= n; i++ {
row[i].min = math.MaxInt
col[i].min = math.MaxInt
}

add := func(m []pair, x, y int) {
m[y].min = min(m[y].min, x)
m[y].max = max(m[y].max, x)
}
isInner := func(m []pair, x, y int) bool {
return m[y].min < x && x < m[y].max
}

for _, p := range buildings {
x, y := p[0], p[1]
add(row, x, y) // x 加到 row[y] 中
add(col, y, x) // y 加到 col[x] 中
}

for _, p := range buildings {
x, y := p[0], p[1]
if isInner(row, x, y) && isInner(col, y, x) {
ans++
}
}
return
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n+m)$，其中 $m$ 是 $\textit{buildings}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

题目说：用计算机 $j$ 解锁计算机 $i$ 的前提是 $j<i$ 且 $\textit{complexity}[j] < \textit{complexity}[i]$。

观察：

• 一开始就解锁的只有计算机 $0$。
• 第一轮，被 $0$ 解锁的计算机（记作集合 $A$），密码复杂度比 $\textit{complexity}[0]$ 大。
• 第二轮，被集合 $A$ 中的计算机解锁的计算机（记作集合 $B$），密码复杂度更大，所以也比 $\textit{complexity}[0]$ 大。
• 第三轮，被集合 $B$ 中的计算机解锁的计算机（记作集合 $C$），密码复杂度更大，所以也比 $\textit{complexity}[0]$ 大。
• 依此类推，所有被解锁的计算机的密码复杂度都要比 $\textit{complexity}[0]$ 大。

定理：当且仅当计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，才能解锁所有计算机。

充分性：如果计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，根据题意，仅用计算机 $0$ 便可解锁所有计算机。

必要性：如果可以解锁所有的计算机，那么计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大。考虑其逆否命题，即如果在计算机 $0$ 的右边存在计算机 $A$，满足 $\textit{complexity}[i] \le \textit{complexity}[0]$，那么不可能解锁计算机 $A$，更不可能解锁所有计算机。为了解锁计算机 $A$，我们需要在其左边找比 $\textit{complexity}[i]$ 更小的计算机。不断往左找，计算机的密码复杂度只会更小，直到找到一台被计算机 $0$ 解锁的计算机 $B$。$B$ 的密码复杂度必须比 $\textit{complexity}[0]$ 大，但为了能解锁计算机 $A$，$B$ 的密码复杂度又要 $< \textit{complexity}[i] \le \textit{complexity}[0]$，矛盾，所以不可能解锁计算机 $A$。

根据定理，如果计算机 $0$ 右边的所有计算机的密码复杂度都比 $\textit{complexity}[0]$ 大，那么我们可以按照任意顺序解锁这 $n-1$ 台计算机，方案数为 $n-1$ 个不同物品的全排列个数，即

$$
(n-1)!
$$

注意取模。关于模运算的知识点，见 模运算的世界：当加减乘除遇上取模。

###py

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        MOD = 1_000_000_007
        ans = 1
        for i in range(1, len(complexity)):
            if complexity[i] <= complexity[0]:
                return 0
            ans = ans * i % MOD
        return ans

###java

class Solution {
    public int countPermutations(int[] complexity) {
        final int MOD = 1_000_000_007;
        long ans = 1;
        for (int i = 1; i < complexity.length; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            ans = ans * i % MOD;
        }
        return (int) ans;
    }
}

###cpp

class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        const int MOD = 1'000'000'007;
        long long ans = 1;
        for (int i = 1; i < complexity.size(); i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            ans = ans * i % MOD;
        }
        return ans;
    }
};

###go

func countPermutations(complexity []int) int {
const mod = 1_000_000_007
ans := 1
for i := 1; i < len(complexity); i++ {
if complexity[i] <= complexity[0] {
return 0
}
ans = ans * i % mod
}
return ans
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{complexity}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

更多相似题目，见下面思维题单的「§5.2 脑筋急转弯」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府