方法一：排序 + 模拟

我们将事件按照时间戳升序排序，如果时间戳相同，我们将 OFFLINE 事件排在 MESSAGE 事件之前。

然后我们模拟事件的发生过程，使用 online_t 数组记录每个用户下一次上线的时间，用一个变量 lazy 记录所有用户还需要被提及的次数。

遍历事件列表，根据事件类型进行处理：

• 如果是 ONLINE 事件，我们更新 online_t 数组；
• 如果是 ALL 事件，我们将 lazy 加一；
• 如果是 HERE 事件，我们遍历 online_t 数组，如果用户下一次上线的时间小于等于当前时间，我们将该用户的提及次数加一；
• 如果是 MESSAGE 事件，我们将提及的用户的提及次数加一。

最后，如果 lazy 大于 0，我们将所有用户的提及次数加上 lazy。

###python

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
        lazy = 0
        for etype, ts, s in events:
            cur = int(ts)
            if etype[0] == "O":
                online_t[int(s)] = cur + 60
            elif s[0] == "A":
                lazy += 1
            elif s[0] == "H":
                for i, t in enumerate(online_t):
                    if t <= cur:
                        ans[i] += 1
            else:
                for a in s.split():
                    ans[int(a[2:])] += 1
        if lazy:
            for i in range(numberOfUsers):
                ans[i] += lazy
        return ans

###java

class Solution {
    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
        events.sort((a, b) -> {
            int x = Integer.parseInt(a.get(1));
            int y = Integer.parseInt(b.get(1));
            if (x == y) {
                return a.get(0).charAt(2) - b.get(0).charAt(2);
            }
            return x - y;
        });
        int[] ans = new int[numberOfUsers];
        int[] onlineT = new int[numberOfUsers];
        int lazy = 0;
        for (var e : events) {
            String etype = e.get(0);
            int cur = Integer.parseInt(e.get(1));
            String s = e.get(2);
            if (etype.charAt(0) == 'O') {
                onlineT[Integer.parseInt(s)] = cur + 60;
            } else if (s.charAt(0) == 'A') {
                ++lazy;
            } else if (s.charAt(0) == 'H') {
                for (int i = 0; i < numberOfUsers; ++i) {
                    if (onlineT[i] <= cur) {
                        ++ans[i];
                    }
                }
            } else {
                for (var a : s.split(" ")) {
                    ++ans[Integer.parseInt(a.substring(2))];
                }
            }
        }
        if (lazy > 0) {
            for (int i = 0; i < numberOfUsers; ++i) {
                ans[i] += lazy;
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        ranges::sort(events, [](const vector<string>& a, const vector<string>& b) {
            int x = stoi(a[1]);
            int y = stoi(b[1]);
            if (x == y) {
                return a[0][2] < b[0][2];
            }
            return x < y;
        });

        vector<int> ans(numberOfUsers, 0);
        vector<int> onlineT(numberOfUsers, 0);
        int lazy = 0;

        for (const auto& e : events) {
            string etype = e[0];
            int cur = stoi(e[1]);
            string s = e[2];

            if (etype[0] == 'O') {
                onlineT[stoi(s)] = cur + 60;
            } else if (s[0] == 'A') {
                lazy++;
            } else if (s[0] == 'H') {
                for (int i = 0; i < numberOfUsers; ++i) {
                    if (onlineT[i] <= cur) {
                        ++ans[i];
                    }
                }
            } else {
                stringstream ss(s);
                string token;
                while (ss >> token) {
                    ans[stoi(token.substr(2))]++;
                }
            }
        }

        if (lazy > 0) {
            for (int i = 0; i < numberOfUsers; ++i) {
                ans[i] += lazy;
            }
        }

        return ans;
    }
};

###go

func countMentions(numberOfUsers int, events [][]string) []int {
sort.Slice(events, func(i, j int) bool {
x, _ := strconv.Atoi(events[i][1])
y, _ := strconv.Atoi(events[j][1])
if x == y {
return events[i][0][2] < events[j][0][2]
}
return x < y
})

ans := make([]int, numberOfUsers)
onlineT := make([]int, numberOfUsers)
lazy := 0

for _, e := range events {
etype := e[0]
cur, _ := strconv.Atoi(e[1])
s := e[2]

if etype[0] == 'O' {
userID, _ := strconv.Atoi(s)
onlineT[userID] = cur + 60
} else if s[0] == 'A' {
lazy++
} else if s[0] == 'H' {
for i := 0; i < numberOfUsers; i++ {
if onlineT[i] <= cur {
ans[i]++
}
}
} else {
mentions := strings.Split(s, " ")
for _, m := range mentions {
userID, _ := strconv.Atoi(m[2:])
ans[userID]++
}
}
}

if lazy > 0 {
for i := 0; i < numberOfUsers; i++ {
ans[i] += lazy
}
}

return ans
}

###ts

function countMentions(numberOfUsers: number, events: string[][]): number[] {
    events.sort((a, b) => {
        const x = +a[1];
        const y = +b[1];
        if (x === y) {
            return a[0].charAt(2) < b[0].charAt(2) ? -1 : 1;
        }
        return x - y;
    });

    const ans: number[] = Array(numberOfUsers).fill(0);
    const onlineT: number[] = Array(numberOfUsers).fill(0);
    let lazy = 0;

    for (const [etype, ts, s] of events) {
        const cur = +ts;
        if (etype.charAt(0) === 'O') {
            const userID = +s;
            onlineT[userID] = cur + 60;
        } else if (s.charAt(0) === 'A') {
            lazy++;
        } else if (s.charAt(0) === 'H') {
            for (let i = 0; i < numberOfUsers; i++) {
                if (onlineT[i] <= cur) {
                    ans[i]++;
                }
            }
        } else {
            const mentions = s.split(' ');
            for (const m of mentions) {
                const userID = +m.slice(2);
                ans[userID]++;
            }
        }
    }

    if (lazy > 0) {
        for (let i = 0; i < numberOfUsers; i++) {
            ans[i] += lazy;
        }
    }

    return ans;
}

时间复杂度 $O(n + m \times \log m \log M + L)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别是用户总数和事件总数，而 $M$ 和 $L$ 分别是时间戳的最大值以及所有提及的字符串的总长度。

---

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

给你一个整数 numberOfUsers 表示用户总数，另有一个大小为 n x 3 的数组 events 。

每个 events[i] 都属于下述两种类型之一：

1. 消息事件（Message Event）：["MESSAGE", "timestampi", "mentions_stringi"]
   • 事件表示在 timestampi 时，一组用户被消息提及。
   • mentions_stringi 字符串包含下述标识符之一：
     • id<number>：其中 <number> 是一个区间 [0,numberOfUsers - 1] 内的整数。可以用单个空格分隔 多个 id ，并且 id 可能重复。此外，这种形式可以提及离线用户。
     • ALL：提及 所有 用户。
     • HERE：提及所有 在线 用户。
2. 离线事件（Offline Event）：["OFFLINE", "timestampi", "idi"]
   • 事件表示用户 idi 在 timestampi 时变为离线状态 60 个单位时间。用户会在 timestampi + 60 时自动再次上线。

返回数组 mentions ，其中 mentions[i] 表示  id 为  i 的用户在所有 MESSAGE 事件中被提及的次数。

最初所有用户都处于在线状态，并且如果某个用户离线或者重新上线，其对应的状态变更将会在所有相同时间发生的消息事件之前进行处理和同步。

注意 在单条消息中，同一个用户可能会被提及多次。每次提及都需要被 分别 统计。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 1 <= numberOfUsers <= 100
• 1 <= events.length <= 100
• events[i].length == 3
• events[i][0] 的值为 MESSAGE 或 OFFLINE 。
• 1 <= int(events[i][1]) <= 105
• 在任意 "MESSAGE" 事件中，以 id<number> 形式提及的用户数目介于 1 和 100 之间。
• 0 <= <number> <= numberOfUsers - 1
• 题目保证 OFFLINE 引用的用户 id 在事件发生时处于 在线 状态。

解法

思路和算法

由于事件发生顺序为时间戳递增顺序，因此应将数组 $\textit{events}$ 按时间戳升序排序，然后遍历数组 $\textit{events}$，根据每个事件更新用户的相应状态。由于相同时间戳的离线和上线事件在消息事件之前处理，因此当存在多个事件的时间戳相同时，离线事件应在消息事件之前。

由于消息事件的提及用户的情况包括提及给定集合的用户、提及所有用户和提及所有在线用户，因此需要判断消息事件发生时每个用户的在线状态，可以通过维护每个用户的最新在线起始时间判断每个用户的在线状态。创建长度为 $\textit{numberOfUsers}$ 的数组 $\textit{onlineTimes}$，其中 $\textit{onlineTimes}[i]$ 表示编号 $i$ 的用户的最新在线起始时间。由于初始时所有用户都处于在线状态且所有事件的时间戳都是正整数，因此将数组 $\textit{onlineTimes}$ 中的所有元素都初始化为 $0$。

创建长度为 $\textit{numberOfUsers}$ 的结果数组 $\textit{mentions}$。遍历排序后的数组 $\textit{events}$，对于遍历到的每个事件 $[\textit{type}, \textit{timestamp}, \textit{users}]$，判断其类型，执行相应的操作。

• 如果 $\textit{types} = \text{``MESSAGE"}$，则当前事件是消息事件，根据 $\textit{users}$ 的值决定需要提及的用户，执行提及操作。

  • 当 $\textit{users} = \text{``ALL"}$ 时，提及所有用户，将数组 $\textit{mentions}$ 中的所有元素值都增加 $1$。

  • 当 $\textit{users} = \text{``HERE"}$ 时，提及所有在线用户，遍历 $0 \le i < \textit{numberOfUsers}$ 的每个用户编号 $i$，如果 $\textit{onlineTimes}[i] \le \textit{timestamp}$，则编号 $i$ 的用户被提及，将 $\textit{mentions}[i]$ 的值增加 $1$。

  • 其余情况下，将 $\textit{users}$ 使用空格分隔转换成数组，遍历数组中的每个用户编号，将用户编号对应的数组 $\textit{mentions}$ 中的元素值增加 $1$。

• 如果 $\textit{types} = \text{``OFFLINE"}$，则当前事件是离线事件，用 $\textit{id}$ 表示 $\textit{users}$ 对应的用户编号，则编号为 $\textit{id}$ 的用户在时间戳 $\textit{timestamp}$ 离线，并将在时间戳 $\textit{timestamp} + 60$ 自动上线，因此将 $\textit{onlineTimes}[\textit{id}]$ 的值更新为 $\textit{timestamp} + 60$。

遍历结束之后，结果数组 $\textit{mentions}$ 即为每个用户被提及的次数。

代码

###Java

class Solution {
    static final String MESSAGE = "MESSAGE", OFFLINE = "OFFLINE", ALL = "ALL", HERE = "HERE";
    static final int OFFLINE_TIME = 60;

    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
        Collections.sort(events, (a, b) -> {
            int aTimestamp = Integer.parseInt(a.get(1)), bTimestamp = Integer.parseInt(b.get(1));
            if (aTimestamp != bTimestamp) {
                return aTimestamp - bTimestamp;
            } else {
                String aType = a.get(0), bType = b.get(0);
                return bType.compareTo(aType);
            }
        });
        int[] mentions = new int[numberOfUsers];
        int[] onlineTimes = new int[numberOfUsers];
        for (List<String> ev : events) {
            String type = ev.get(0);
            int timestamp = Integer.parseInt(ev.get(1));
            String users = ev.get(2);
            if (MESSAGE.equals(type)) {
                if (ALL.equals(users)) {
                    updateMentions(mentions, onlineTimes, Integer.MAX_VALUE);
                } else if (HERE.equals(users)) {
                    updateMentions(mentions, onlineTimes, timestamp);
                } else {
                    String[] ids = users.split(" ");
                    for (String idStr : ids) {
                        int id = Integer.parseInt(idStr.substring(2));
                        mentions[id]++;
                    }
                }
            } else {
                int id = Integer.parseInt(users);
                onlineTimes[id] = timestamp + OFFLINE_TIME;
            }
        }
        return mentions;
    }

    public void updateMentions(int[] mentions, int[] onlineTimes, int timestamp) {
        int numberOfUsers = mentions.length;
        for (int i = 0; i < numberOfUsers; i++) {
            if (onlineTimes[i] <= timestamp) {
                mentions[i]++;
            }
        }
    }
}

###C#

public class Solution {
    const string MESSAGE = "MESSAGE", OFFLINE = "OFFLINE", ALL = "ALL", HERE = "HERE";
    const int OFFLINE_TIME = 60;

    public int[] CountMentions(int numberOfUsers, IList<IList<string>> events) {
        ((List<IList<string>>) events).Sort((a, b) => {
            int aTimestamp = int.Parse(a[1]), bTimestamp = int.Parse(b[1]);
            if (aTimestamp != bTimestamp) {
                return aTimestamp - bTimestamp;
            } else {
                string aType = a[0], bType = b[0];
                return bType.CompareTo(aType);
            }
        });
        int[] mentions = new int[numberOfUsers];
        int[] onlineTimes = new int[numberOfUsers];
        foreach (IList<string> ev in events) {
            string type = ev[0];
            int timestamp = int.Parse(ev[1]);
            string users = ev[2];
            if (MESSAGE.Equals(type)) {
                if (ALL.Equals(users)) {
                    UpdateMentions(mentions, onlineTimes, int.MaxValue);
                } else if (HERE.Equals(users)) {
                    UpdateMentions(mentions, onlineTimes, timestamp);
                } else {
                    string[] ids = users.Split(" ");
                    foreach (string idStr in ids) {
                        int id = int.Parse(idStr.Substring(2));
                        mentions[id]++;
                    }
                }
            } else {
                int id = int.Parse(users);
                onlineTimes[id] = timestamp + OFFLINE_TIME;
            }
        }
        return mentions;
    }

    public void UpdateMentions(int[] mentions, int[] onlineTimes, int timestamp) {
        int numberOfUsers = mentions.Length;
        for (int i = 0; i < numberOfUsers; i++) {
            if (onlineTimes[i] <= timestamp) {
                mentions[i]++;
            }
        }
    }
}

复杂度分析

• 时间复杂度：$O(n \log n \log t + \textit{numberOfUsers} + L)$，其中 $n$ 是数组 $\textit{events}$ 的长度，$\textit{numberOfUsers}$ 是用户总数，$t$ 是数组 $\textit{events}$ 中的时间戳最大值，$L$ 是数组 $\textit{events}$ 中的所有提及字符串的长度之和。将数组 $\textit{events}$ 排序的时间是 $O(n \log n \log t)$，创建数组 $\textit{mentions}$ 和 $\textit{onlineTimes}$ 的时间是 $O(\textit{numberOfUsers})$，遍历排序后的数组 $\textit{events}$ 计算提及次数的时间是 $O(n + L)$，因此时间复杂度是 $O(n \log n \log t + \textit{numberOfUsers} + L)$。

• 空间复杂度：$O(n + \textit{numberOfUsers})$，其中 $n$ 是数组 $\textit{events}$ 的长度，$\textit{numberOfUsers}$ 是用户总数。由于待排序的元素是数组，因此排序的空间是 $O(n)$，记录每个用户的最新在线起始时间的空间是 $O(\textit{numberOfUsers})$。

方法一：模拟

先说暴力怎么做。

注意输入的 $\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

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& cnt : ans) {
                    cnt++;
                }
            } 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))]++;
            }
        }
    }
    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)$。

方法二：计算离线期间被提及的次数

对于 ALL 消息，用一个变量 $\textit{all}$ 统计所有用户被提及的次数。

对于 HERE 消息：

1. 先认为所有用户都被提及了，把 $\textit{all}$ 加一。
2. 此刻离线的用户不能被计入，需要把这些用户的提及次数减一。

比如一个用户在 $5$ 时刻离线，在 $65$ 时刻在线，那么发生在 $[5,64]$ 中的 HERE 消息个数，就是需要减去的提及次数。

借鉴 前缀和 的思想，用 $[0,64]$ 中的 HERE 消息个数，减去 $[0,4]$ 中的 HERE 消息个数，即为 $[5,64]$ 中的 HERE 消息个数。

把离线事件、上线事件、HERE 消息混在一起，按照发生时间排序。相同时间的，HERE 消息排在后面。然后遍历这些事件，同时统计 HERE 消息个数 $\textit{here}$。离线时加上 $\textit{here}$，在线时减去 $\textit{here}$。这样一加一减，最终减去的就是离线时的 HERE 消息个数。

###py

class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
        ans = [0] * numberOfUsers
        es = []  # (timestamp, type, id)
        all = 0
        for type_, timestamp, mention in events:
            cur_t = int(timestamp)  # 当前时间
            if type_[0] == 'O':  # 离线
                i = int(mention)
                es.append((cur_t, 1, i))
                es.append((cur_t + 60, -1, i))
            elif mention[0] == 'A':  # @所有人
                all += 1
            elif mention[0] == 'H':  # @所有在线用户
                all += 1
                es.append((cur_t, 2, -1))
            else:  # @id
                for s in mention.split():
                    ans[int(s[2:])] += 1

        es.sort()

        here = 0
        for _, type_, i in es:
            if type_ == 2:
                here += 1
            else:
                # 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
                ans[i] += type_ * here  # type=1 是加，-1 是减

        for i in range(numberOfUsers):
            ans[i] += all
        return ans

###java

class Solution {
    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
        int[] ans = new int[numberOfUsers];
        List<int[]> es = new ArrayList<>(); // (timestamp, type, id)
        int all = 0;
        for (List<String> e : events) {
            int curT = Integer.parseInt(e.get(1)); // 当前时间
            String mention = e.get(2);
            if (e.get(0).charAt(0) == 'O') { // 离线
                int i = Integer.parseInt(mention);
                es.add(new int[]{curT, 1, i});
                es.add(new int[]{curT + 60, -1, i});
            } else if (mention.charAt(0) == 'A') { // @所有人
                all++;
            } else if (mention.charAt(0) == 'H') { // @所有在线用户
                all++;
                es.add(new int[]{curT, 2, -1});
            } else { // @id
                for (String s : mention.split(" ")) {
                    int i = Integer.parseInt(s.substring(2));
                    ans[i]++;
                }
            }
        }

        es.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

        int here = 0;
        for (int[] e : es) {
            int type = e[1];
            if (type == 2) {
                here++;
            } else {
                // 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
                ans[e[2]] += type * here; // type=1 是加，-1 是减
            }
        }

        for (int i = 0; i < numberOfUsers; i++) {
            ans[i] += all;
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        vector<int> ans(numberOfUsers);
        vector<tuple<int, int, int>> es; // (timestamp, type, id)
        int all = 0;
        for (auto& e : events) {
            int cur_t = stoi(e[1]); // 当前时间
            string mention = e[2];
            if (e[0][0] == 'O') { // 离线
                int i = stoi(mention);
                es.emplace_back(cur_t, 1, i);
                es.emplace_back(cur_t + 60, -1, i);
            } else if (mention[0] == 'A') { // @所有人
                all++;
            } else if (mention[0] == 'H') { // @所有在线用户
                all++;
                es.emplace_back(cur_t, 2, -1);
            } else { // @id
                for (const auto& part : mention | ranges::views::split(' ')) {
                    string s(part.begin() + 2, part.end());
                    ans[stoi(s)]++;
                }
            }
        }

        ranges::sort(es);

        int here = 0;
        for (auto& [_, type, id] : es) {
            if (type == 2) {
                here++;
            } else {
                // 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
                ans[id] += type * here; // type=1 是加，-1 是减
            }
        }

        for (int& cnt : ans) {
            cnt += all;
        }
        return ans;
    }
};

###c

typedef struct {
    int timestamp;
    int type;
    int id;
} Event;

int cmp(const void* a, const void* b) {
    Event* x = (Event*) a;
    Event* y = (Event*) b;
    return x->timestamp != y->timestamp ? x->timestamp - y->timestamp : x->type - y->type;
}

int* countMentions(int numberOfUsers, char*** events, int eventsSize, int* eventsColSize, int* returnSize) {
    *returnSize = numberOfUsers;
    int* ans = calloc(numberOfUsers, sizeof(int));
    Event* es = malloc(eventsSize * 2 * sizeof(Event));
    int es_size = 0;
    int all = 0;

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

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

    qsort(es, es_size, sizeof(Event), cmp);

    int here = 0;
    for (int i = 0; i < es_size; i++) {
        Event e = es[i];
        if (e.type == 2) {
            here++;
        } else {
            // 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
            ans[e.id] += e.type * here; // type=1 是加，-1 是减
        }
    }

    for (int i = 0; i < numberOfUsers; i++) {
        ans[i] += all;
    }

    free(es);
    return ans;
}

###go

func countMentions(numberOfUsers int, events [][]string) []int {
ans := make([]int, numberOfUsers)
type event struct{ timestamp, type_, id int }
es := []event{}
all := 0
for _, e := range events {
curT, _ := strconv.Atoi(e[1]) // 当前时间
mention := e[2]
if e[0][0] == 'O' { // 离线
i, _ := strconv.Atoi(mention)
es = append(es, event{curT, 1, i}, event{curT + 60, -1, i})
} else if mention[0] == 'A' { // @所有人
all++
} else if mention[0] == 'H' { // @所有在线用户
all++
es = append(es, event{curT, 2, -1})
} else { // @id
for _, s := range strings.Split(mention, " ") {
i, _ := strconv.Atoi(s[2:])
ans[i]++
}
}
}

slices.SortFunc(es, func(a, b event) int {
return cmp.Or(a.timestamp-b.timestamp, a.type_-b.type_)
})

here := 0
for _, e := range es {
if e.type_ == 2 {
here++
} else {
// 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
ans[e.id] += e.type_ * here // type=1 是加，-1 是减 
}
}

for i := range ans {
ans[i] += all
}
return ans
}

###js

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

    es.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

    let here = 0;
    for (const [_, type, id] of es) {
        if (type === 2) {
            here++;
        } else {
            // 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
            ans[id] += type * here; // type=1 是加，-1 是减
        }
    }

    for (let i = 0; i < numberOfUsers; i++) {
        ans[i] += all;
    }
    return ans;
};

###rust

impl Solution {
    pub fn count_mentions(number_of_users: i32, events: Vec<Vec<String>>) -> Vec<i32> {
        let n = number_of_users as usize;
        let mut ans = vec![0; n];
        let mut es = vec![]; // (timestamp, type, id)
        let mut all = 0;
        for e in events {
            let cur_t = e[1].parse::<i32>().unwrap(); // 当前时间
            let mention = &e[2];
            if e[0].as_bytes()[0] == b'O' { // 离线
                let i = mention.parse::<usize>().unwrap();
                es.push((cur_t, 1, i));
                es.push((cur_t + 60, -1, i));
            } else if mention.as_bytes()[0] == b'A' { // @所有人
                all += 1;
            } else if mention.as_bytes()[0] == b'H' { // @所有在线用户
                all += 1;
                es.push((cur_t, 2, 0));
            } else { // @id
                for s in mention.split(' ') {
                    ans[s[2..].parse::<usize>().unwrap()] += 1;
                }
            }
        }

        es.sort_unstable();

        let mut here = 0;
        for (_, type_, id) in es {
            if type_ == 2 {
                here += 1;
            } else {
                // 注意 HERE 排在后面，还没有计入发生在此刻的 HERE 消息
                ans[id] += type_ * here; // type=1 是加，-1 是减
            }
        }

        for cnt in ans.iter_mut() {
            *cnt += all;
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n + m\log m + L)$，其中 $m$ 是 $\textit{events}$ 的长度，$n$ 是 $\textit{numberOfUsers}$，$L$ 是所有 timestamp 和 mentions_string 的长度之和。除了排序，其余逻辑均为线性。
• 空间复杂度：$\mathcal{O}(n + m)$。

分类题单

如何科学刷题？

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站@灵茶山艾府

方法一：哈希表 + 排序

我们可以将建筑按照横坐标和纵坐标进行分组，分别记录在哈希表 $\text{g1}$ 和 $\text{g2}$ 中，其中 $\text{g1[x]}$ 表示所有横坐标为 $x$ 的纵坐标，而 $\text{g2[y]}$ 表示所有纵坐标为 $y$ 的横坐标，然后我们将其进行排序。

接下来，我们遍历所有建筑，对于当前建筑 $(x, y)$，我们通过哈希表获取对应的纵坐标列表 $l_1$ 和横坐标列表 $l_2$，并检查条件以确定建筑是否被覆盖。覆盖的条件是 $l_2[0] < x < l_2[-1]$ 且 $l_1[0] < y < l_1[-1]$，若是，我们将答案加一。

遍历结束后，返回答案即可。

###python

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        g1 = defaultdict(list)
        g2 = defaultdict(list)
        for x, y in buildings:
            g1[x].append(y)
            g2[y].append(x)
        for x in g1:
            g1[x].sort()
        for y in g2:
            g2[y].sort()
        ans = 0
        for x, y in buildings:
            l1 = g1[x]
            l2 = g2[y]
            if l2[0] < x < l2[-1] and l1[0] < y < l1[-1]:
                ans += 1
        return ans

###java

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        Map<Integer, List<Integer>> g1 = new HashMap<>();
        Map<Integer, List<Integer>> g2 = new HashMap<>();

        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            g1.computeIfAbsent(x, k -> new ArrayList<>()).add(y);
            g2.computeIfAbsent(y, k -> new ArrayList<>()).add(x);
        }

        for (var e : g1.entrySet()) {
            Collections.sort(e.getValue());
        }
        for (var e : g2.entrySet()) {
            Collections.sort(e.getValue());
        }

        int ans = 0;

        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            List<Integer> l1 = g1.get(x);
            List<Integer> l2 = g2.get(y);

            if (l2.get(0) < x && x < l2.get(l2.size() - 1) && l1.get(0) < y
                && y < l1.get(l1.size() - 1)) {
                ans++;
            }
        }

        return ans;
    }
}

###cpp

class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        unordered_map<int, vector<int>> g1;
        unordered_map<int, vector<int>> g2;

        for (const auto& building : buildings) {
            int x = building[0], y = building[1];
            g1[x].push_back(y);
            g2[y].push_back(x);
        }

        for (auto& e : g1) {
            sort(e.second.begin(), e.second.end());
        }
        for (auto& e : g2) {
            sort(e.second.begin(), e.second.end());
        }

        int ans = 0;

        for (const auto& building : buildings) {
            int x = building[0], y = building[1];
            const vector<int>& l1 = g1[x];
            const vector<int>& l2 = g2[y];

            if (l2[0] < x && x < l2[l2.size() - 1] && l1[0] < y && y < l1[l1.size() - 1]) {
                ans++;
            }
        }

        return ans;
    }
};

###go

func countCoveredBuildings(n int, buildings [][]int) (ans int) {
g1 := make(map[int][]int)
g2 := make(map[int][]int)

for _, building := range buildings {
x, y := building[0], building[1]
g1[x] = append(g1[x], y)
g2[y] = append(g2[y], x)
}

for _, list := range g1 {
sort.Ints(list)
}
for _, list := range g2 {
sort.Ints(list)
}

for _, building := range buildings {
x, y := building[0], building[1]
l1 := g1[x]
l2 := g2[y]

if l2[0] < x && x < l2[len(l2)-1] && l1[0] < y && y < l1[len(l1)-1] {
ans++
}
}
return
}

###ts

function countCoveredBuildings(n: number, buildings: number[][]): number {
    const g1: Map<number, number[]> = new Map();
    const g2: Map<number, number[]> = new Map();

    for (const [x, y] of buildings) {
        if (!g1.has(x)) g1.set(x, []);
        g1.get(x)?.push(y);

        if (!g2.has(y)) g2.set(y, []);
        g2.get(y)?.push(x);
    }

    for (const list of g1.values()) {
        list.sort((a, b) => a - b);
    }
    for (const list of g2.values()) {
        list.sort((a, b) => a - b);
    }

    let ans = 0;

    for (const [x, y] of buildings) {
        const l1 = g1.get(x)!;
        const l2 = g2.get(y)!;

        if (l2[0] < x && x < l2[l2.length - 1] && l1[0] < y && y < l1[l1.length - 1]) {
            ans++;
        }
    }

    return ans;
}

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是建筑物的数量。

---

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个 唯一 建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。

返回 被覆盖 的建筑数量。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 2 <= n <= 105
• 1 <= buildings.length <= 105
• buildings[i] = [x, y]
• 1 <= x, y <= n
• buildings 中所有坐标均 唯一 。

解法一

思路和算法

根据建筑被覆盖的定义，当一个建筑在四个方向都至少存在一个其他建筑时，该建筑被覆盖。为了计算被覆盖的建筑数量，需要分别判断每个建筑是否被覆盖，因此需要分别统计每个 $x$ 坐标和每个 $y$ 坐标的所有建筑的列表。

使用两个哈希表分别记录每个 $x$ 坐标的所有建筑列表和每个 $y$ 坐标的所有建筑列表，两个哈希表分别为 $x$ 分组哈希表和 $y$ 分组哈希表。遍历数组 $\textit{buildings}$ 将所有建筑加入两个哈希表，然后将两个哈希表中的每个 $x$ 坐标和 $y$ 坐标对应的建筑列表排序，排序方法如下：在 $x$ 分组哈希表中，将每个 $x$ 坐标的所有建筑列表按 $y$ 坐标升序排序；在 $y$ 分组哈希表中，将每个 $y$ 坐标的所有建筑列表按 $x$ 坐标升序排序。

排序结束之后，即可判断每个建筑在 $x$ 坐标方向和 $y$ 坐标方向是否被覆盖。遍历所有建筑，对于位于坐标 $(x, y)$ 的建筑，判断方法如下。

• 从 $y$ 分组哈希表中得到该建筑的相同 $y$ 坐标的所有建筑的列表，列表已经按 $x$ 坐标升序排序，判断当前 $x$ 坐标是否为列表中的最小值或最大值，如果既不是最小值也不是最大值，则该建筑在 $x$ 坐标方向被覆盖。

• 从 $x$ 分组哈希表中得到该建筑的相同 $x$ 坐标的所有建筑的列表，列表已经按 $y$ 坐标升序排序，判断当前 $y$ 坐标是否为列表中的最小值或最大值，如果既不是最小值也不是最大值，则该建筑在 $y$ 坐标方向被覆盖。

当一个建筑同时在 $x$ 坐标方向和 $y$ 坐标方向被覆盖时，该建筑被覆盖。

遍历结束之后，即可得到被覆盖的建筑数量。

代码

###Java

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        Map<Integer, List<Integer>> xToBuildings = new HashMap<Integer, List<Integer>>();
        Map<Integer, List<Integer>> yToBuildings = new HashMap<Integer, List<Integer>>();
        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            xToBuildings.putIfAbsent(x, new ArrayList<Integer>());
            xToBuildings.get(x).add(y);
            yToBuildings.putIfAbsent(y, new ArrayList<Integer>());
            yToBuildings.get(y).add(x);
        }
        Set<Map.Entry<Integer, List<Integer>>> xEntries = xToBuildings.entrySet();
        Set<Map.Entry<Integer, List<Integer>>> yEntries = yToBuildings.entrySet();
        for (Map.Entry<Integer, List<Integer>> entry : xEntries) {
            Collections.sort(entry.getValue());
        }
        for (Map.Entry<Integer, List<Integer>> entry : yEntries) {
            Collections.sort(entry.getValue());
        }
        int count = 0;
        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            List<Integer> xList = yToBuildings.get(y);
            List<Integer> yList = xToBuildings.get(x);
            int xMin = xList.get(0), xMax = xList.get(xList.size() - 1);
            int yMin = yList.get(0), yMax = yList.get(yList.size() - 1);
            if (x > xMin && x < xMax && y > yMin && y < yMax) {
                count++;
            }
        }
        return count;
    }
}

###C#

public class Solution {
    public int CountCoveredBuildings(int n, int[][] buildings) {
        IDictionary<int, IList<int>> xToBuildings = new Dictionary<int, IList<int>>();
        IDictionary<int, IList<int>> yToBuildings = new Dictionary<int, IList<int>>();
        foreach (int[] building in buildings) {
            int x = building[0], y = building[1];
            xToBuildings.TryAdd(x, new List<int>());
            xToBuildings[x].Add(y);
            yToBuildings.TryAdd(y, new List<int>());
            yToBuildings[y].Add(x);
        }
        foreach (KeyValuePair<int, IList<int>> pair in xToBuildings) {
            ((List<int>) pair.Value).Sort();
        }
        foreach (KeyValuePair<int, IList<int>> pair in yToBuildings) {
            ((List<int>) pair.Value).Sort();
        }
        int count = 0;
        foreach (int[] building in buildings) {
            int x = building[0], y = building[1];
            IList<int> xIList = yToBuildings[y];
            IList<int> yIList = xToBuildings[x];
            int xMin = xIList[0], xMax = xIList[xIList.Count - 1];
            int yMin = yIList[0], yMax = yIList[yIList.Count - 1];
            if (x > xMin && x < xMax && y > yMin && y < yMax) {
                count++;
            }
        }
        return count;
    }
}

复杂度分析

• 时间复杂度：$O(m \log m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。将所有建筑存入两个哈希表的时间是 $O(m)$，排序的时间是 $O(m \log m)$，排序之后计算被覆盖的建筑数量的时间是 $O(m)$，因此时间复杂度是 $O(m \log m)$。

• 空间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。哈希表的空间是 $O(m)$。

解法二

思路和算法

判断一个建筑是否被覆盖时，需要知道如下信息。

• 在相同 $y$ 坐标的所有建筑的列表中，该建筑的 $x$ 坐标是否为列表中的最小值或最大值。

• 在相同 $x$ 坐标的所有建筑的列表中，该建筑的 $y$ 坐标是否为列表中的最小值或最大值。

因此，不需要维护每个 $x$ 坐标和每个 $y$ 坐标的所有建筑，只需要维护每个 $x$ 坐标的最小 $y$ 坐标和最大 $y$ 坐标，以及每个 $y$ 坐标的最小 $x$ 坐标和最大 $x$ 坐标。遍历数组 $\textit{buildings}$ 之后，将最小坐标与最大坐标的信息存入哈希表。再次遍历数组，即可根据哈希表中的最小坐标与最大坐标的信息判断每个建筑是否被覆盖，计算被覆盖的建筑数量。

代码

###Java

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        Map<Integer, int[]> xToMinMax = new HashMap<Integer, int[]>();
        Map<Integer, int[]> yToMinMax = new HashMap<Integer, int[]>();
        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            xToMinMax.putIfAbsent(x, new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE});
            int[] yMinMax = xToMinMax.get(x);
            yMinMax[0] = Math.min(yMinMax[0], y);
            yMinMax[1] = Math.max(yMinMax[1], y);
            yToMinMax.putIfAbsent(y, new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE});
            int[] xMinMax = yToMinMax.get(y);
            xMinMax[0] = Math.min(xMinMax[0], x);
            xMinMax[1] = Math.max(xMinMax[1], x);
        }
        int count = 0;
        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            int[] xMinMax = yToMinMax.get(y);
            int[] yMinMax = xToMinMax.get(x);
            int xMin = xMinMax[0], xMax = xMinMax[1];
            int yMin = yMinMax[0], yMax = yMinMax[1];
            if (x > xMin && x < xMax && y > yMin && y < yMax) {
                count++;
            }
        }
        return count;
    }
}

###C#

public class Solution {
    public int CountCoveredBuildings(int n, int[][] buildings) {
        IDictionary<int, int[]> xToMinMax = new Dictionary<int, int[]>();
        IDictionary<int, int[]> yToMinMax = new Dictionary<int, int[]>();
        foreach (int[] building in buildings) {
            int x = building[0], y = building[1];
            xToMinMax.TryAdd(x, new int[]{int.MaxValue, int.MinValue});
            int[] yMinMax = xToMinMax[x];
            yMinMax[0] = Math.Min(yMinMax[0], y);
            yMinMax[1] = Math.Max(yMinMax[1], y);
            yToMinMax.TryAdd(y, new int[]{int.MaxValue, int.MinValue});
            int[] xMinMax = yToMinMax[y];
            xMinMax[0] = Math.Min(xMinMax[0], x);
            xMinMax[1] = Math.Max(xMinMax[1], x);
        }
        int count = 0;
        foreach (int[] building in buildings) {
            int x = building[0], y = building[1];
            int[] xMinMax = yToMinMax[y];
            int[] yMinMax = xToMinMax[x];
            int xMin = xMinMax[0], xMax = xMinMax[1];
            int yMin = yMinMax[0], yMax = yMinMax[1];
            if (x > xMin && x < xMax && y > yMin && y < yMax) {
                count++;
            }
        }
        return count;
    }
}

复杂度分析

• 时间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。遍历所有建筑维护两个哈希表的时间是 $O(m)$，计算被覆盖的建筑数量的时间是 $O(m)$，因此时间复杂度是 $O(m)$。

• 空间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。哈希表的空间是 $O(m)$。

分析

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

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

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

算法

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

对于每个建筑 $(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站@灵茶山艾府

解法：模拟

把 $x$ 值相同的建筑放在一个 vector 里，对它们的 $y$ 值排序，就能知道每个建筑上下有没有其它建筑。左右的处理类似。

复杂度 $\mathcal{O}(n\log n)$。

参考代码（c++）

class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        int m = buildings.size();
        int cnt[m];
        memset(cnt, 0, sizeof(cnt));

        typedef pair<int, int> pii;
        // 把 x 值相同的建筑放在同一个 vector 里，对它们的 y 值排序
        unordered_map<int, vector<pii>> X;
        // 把 y 值相同的建筑放在同一个 vector 里，对它们的 x 值排序
        unordered_map<int, vector<pii>> Y;
        for (int i = 0; i < m; i++) {
            X[buildings[i][0]].push_back({buildings[i][1], i});
            Y[buildings[i][1]].push_back({buildings[i][0], i});
        }

        for (auto &p : X) {
            auto &vec = p.second;
            sort(vec.begin(), vec.end());
            // 标记下面有其它建筑的房子
            for (int i = 1; i < vec.size(); i++) cnt[vec[i].second]++;
            // 标记上面有其它建筑的房子
            for (int i = 0; i + 1 < vec.size(); i++) cnt[vec[i].second]++;
        }
        for (auto &p : Y) {
            auto &vec = p.second;
            sort(vec.begin(), vec.end());
            // 标记左面有其它建筑的房子
            for (int i = 1; i < vec.size(); i++) cnt[vec[i].second]++;
            // 标记右面有其它建筑的房子
            for (int i = 0; i + 1 < vec.size(); i++) cnt[vec[i].second]++;
        }

        int ans = 0;
        // 需要有 4 个标记
        for (int i = 0; i < m; i++) if (cnt[i] == 4) ans++;
        return ans;
    }
};

方法一：脑筋急转弯

由于编号为 $0$ 的计算机密码已经被解锁，那么对于其他计算机 $i$，如果存在 $\text{complexity}[i] \leq \text{complexity}[0]$，则无法解锁计算机 $i$，因此返回 $0$。否则，排列可以是任意的，一共有 $(n - 1)!$ 种排列方式。

###python

class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        mod = 10**9 + 7
        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 = (int) 1e9 + 7;
        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 = 1e9 + 7;
        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 {
mod := int64(1e9 + 7)
ans := int64(1)
for i := 1; i < len(complexity); i++ {
if complexity[i] <= complexity[0] {
return 0
}
ans = ans * int64(i) % mod
}
return int(ans)
}

###ts

function countPermutations(complexity: number[]): number {
    const mod = 1e9 + 7;
    let ans = 1;
    for (let i = 1; i < complexity.length; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        ans = (ans * i) % mod;
    }
    return ans;
}

###rust

impl Solution {
    pub fn count_permutations(complexity: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut ans = 1i64;
        for i in 1..complexity.len() {
            if complexity[i] <= complexity[0] {
                return 0;
            }
            ans = ans * i as i64 % MOD;
        }
        ans as i32
    }
}

时间复杂度 $O(n)$，其中 $n$ 是数组 $\text{complexity}$ 的长度。空间复杂度 $O(1)$。

---

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

给你一个长度为 n 的数组 complexity。

在房间里有 n 台 上锁的 计算机，这些计算机的编号为 0 到 n - 1，每台计算机都有一个 唯一 的密码。编号为 i 的计算机的密码复杂度为 complexity[i]。

编号为 0 的计算机密码已经 解锁 ，并作为根节点。其他所有计算机必须通过它或其他已经解锁的计算机来解锁，具体规则如下：

• 可以使用编号为 j 的计算机的密码解锁编号为 i 的计算机，其中 j 是任何小于 i 的整数，且满足 complexity[j] < complexity[i]（即 j < i 并且 complexity[j] < complexity[i]）。
• 要解锁编号为 i 的计算机，你需要事先解锁一个编号为 j 的计算机，满足 j < i 并且 complexity[j] < complexity[i]。

求共有多少种 [0, 1, 2, ..., (n - 1)] 的排列方式，能够表示从编号为 0 的计算机（唯一初始解锁的计算机）开始解锁所有计算机的有效顺序。

由于答案可能很大，返回结果需要对 10⁹ + 7 取余数。

注意：编号为 0 的计算机的密码已解锁，而 不是 排列中第一个位置的计算机密码已解锁。

排列 是一个数组中所有元素的重新排列。

 

示例 1：

示例 2：

 

提示：

• 2 <= complexity.length <= 105
• 1 <= complexity[i] <= 109

解法

思路和算法

使用已解锁的计算机密码将未解锁的计算机解锁的条件是：已解锁的计算机的编号和密码复杂度分别小于未解锁的计算机的编号和密码复杂度。由于初始时只有编号为 $0$ 的计算机密码已解锁，编号 $0$ 是最小编号，因此对于其他任意编号 $i$，是否可以使用编号为 $0$ 的计算机密码解锁编号为 $i$ 的计算机的情况如下。

• 当 $\textit{complexity}[i] > \textit{complexity}[0]$ 时，可以使用编号为 $0$ 的计算机密码解锁编号为 $i$ 的计算机。

• 当 $\textit{complexity}[i] \le \textit{complexity}[0]$ 时，不能使用编号为 $0$ 的计算机密码解锁编号为 $i$ 的计算机。

如果存在 $1 \le i < n$ 的整数 $i$ 满足 $\textit{complexity}[i] \le \textit{complexity}[0]$，则对于任意可以被编号为 $0$ 的计算机密码解锁的计算机的编号 $j$，必有 $\textit{complexity}[j] > \textit{complexity}[0]$，因此 $\textit{complexity}[j] > \textit{complexity}[i]$，即编号为 $j$ 的计算机密码不能解锁编号为 $i$ 的计算机。因此，编号为 $i$ 的计算机无法被解锁，此时无法解锁所有计算机。

如果 $1 \le i < n$ 的所有整数 $i$ 都满足 $\textit{complexity}[i] > \textit{complexity}[0]$，则所有计算机都能被编号为 $0$ 的计算机密码解锁。由于初始时编号为 $0$ 的计算机密码已解锁，因此其余 $n - 1$ 台计算机可以按任意顺序解锁，排列数是 $(n - 1)!$。

代码

###Java

class Solution {
    static final int MODULO = 1000000007;

    public int countPermutations(int[] complexity) {
        long permutations = 1;
        int n = complexity.length;
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            permutations = permutations * i % MODULO;
        }
        return (int) permutations;
    }
}

###C#

public class Solution {
    const int MODULO = 1000000007;

    public int CountPermutations(int[] complexity) {
        long permutations = 1;
        int n = complexity.Length;
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            permutations = permutations * i % MODULO;
        }
        return (int) permutations;
    }
}

###C++

const int MODULO = 1000000007;

class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        long long permutations = 1;
        int n = complexity.size();
        for (int i = 1; i < n; i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            permutations = permutations * i % MODULO;
        }
        return permutations;
    }
};

###Python

MODULO = 1000000007

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

###C

const int MODULO = 1000000007;

int countPermutations(int* complexity, int complexitySize) {
    long long permutations = 1;
    for (int i = 1; i < complexitySize; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        permutations = permutations * i % MODULO;
    }
    return permutations;
}

###Go

const MODULO = 1000000007

func countPermutations(complexity []int) int {
    permutations := 1
    n := len(complexity)
    for i := 1; i < n; i++ {
        if complexity[i] <= complexity[0] {
            return 0
        }
        permutations = permutations * i % MODULO
    }
    return permutations
}

###JavaScript

const MODULO = 1000000007;

var countPermutations = function(complexity) {
    let permutations = 1;
    let n = complexity.length;
    for (let i = 1; i < n; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        permutations = permutations * i % MODULO;
    }
    return permutations;
};

###TypeScript

const MODULO = 1000000007;

function countPermutations(complexity: number[]): number {
    let permutations = 1;
    let n = complexity.length;
    for (let i = 1; i < n; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        permutations = permutations * i % MODULO;
    }
    return permutations;
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{complexity}$ 的长度。需要遍历数组一次。

• 空间复杂度：$O(1)$。

题目说：用计算机 $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站@灵茶山艾府

解法：分类讨论

因为只能用小 complexity 解锁大 complexity，所以后续解锁的电脑一定满足 complexity[i] > complexity[0]。

换句话说，如果存在 i > 0，使得 complexity[i] <= complexity[0]，那就无法解锁该电脑，答案为 $0$。

否则，所有电脑都能通过电脑 $0$ 解锁，因此后续编号可以任意排列，答案为 $(n - 1)!$。

复杂度 $\mathcal{O}(n)$。

参考代码（c++）

class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        int n = complexity.size();

        // 检查是否有无法解锁的电脑
        for (int i = 1; i < n; i++) if (complexity[i] <= complexity[0]) return 0;

        // 计算 (n - 1)!
        const int MOD = 1e9 + 7;
        long long ans = 1;
        for (int i = 1; i < n; i++) ans = ans * i % MOD;
        return ans;
    }
};