Leetcode 636

Leetcode 636: Exclusive Time of Functions

题目描述：

给定一个单线程的 CPU，这个 CPU 有 n 个需要运行的函数，函数编号从 0 到 n-1。在存储器里，函数以 [s, e, id] 的形式存储，其中 s 表示这个函数开始的时间，e 表示这个函数结束的时间，函数 id 表示这个函数的编号。给定一个日志，格式化字符串表示函数的调用情况，其格式如下：

Function ID:StartOrEnd:Timestamp

例如：

0:start:0
1:start:2
1:end:5
0:end:6

表示函数 0 在时间戳 0 的时候开始，在时间戳 6 的时候结束；而函数 1 在时间戳 2 的时候开始，在时间戳 5 的时候结束。函数 0 和函数 1 都执行了一个时间段，函数 1 执行了两个时间段。

请你返回一个表示每个函数执行时间的数组 answer，数组中第 i 个元素表示为函数 i 执行的时间，其中 0 <= i < n。

函数的执行时间是指函数的结束时间减去函数的开始时间。如果一个函数在调用期间没有被其他函数中断，那么它的执行时间就是这个函数的结束时间减去开始时间。如果一个函数在调用期间被其他函数中断，那么它的执行时间就是它的最后一个结束时间减去它的开始时间。保证函数的调用顺序是按照函数编号的升序来表示的。

示例 1：

输入：
n = 2
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
输出：[3, 4]
解释：
函数 0 在时间戳 0 的时候开始，在时间戳 6 的时候结束，执行时间为 6 - 0 = 6 秒。
函数 1 在时间戳 2 的时候开始，在时间戳 5 的时候结束，执行时间为 5 - 2 = 3 秒。
示例 2：

输入：
n = 1
logs = ["0:start:0","0:end:0"]
输出：[1]
解释：
函数 0 在时间戳 0 的时候开始，在时间戳 0 的时候结束，执行时间为 0 秒。
注意：函数调用会存在嵌套情况，例如上例中的logs。函数调用顺序不会超过 1000。函数的最大执行时间为 999ms，保证整数部分不超过 10^7。

解题思路：

这道题是要求每个函数的执行时间，我们可以使用一个栈来维护每个函数的开始和结束时间，遍历 logs，遇到一个函数开始就将其入栈，遇到一个函数结束就将栈顶元素弹出。由于栈中存储的是函数的开始时间，所以结束时间需要减去栈顶元素的开始时间来计算这个函数的执行时间。如果遇到的是函数结束操作，那么栈顶元素就是这个函数的开始时间，需要将它弹出，但是后面的函数可能会依赖于这个栈顶元素，所以需要先计算弹出栈顶元素后的执行时间，再将栈顶元素弹出。

时间复杂度：O(n)

空间复杂度：O(n)

参考代码：