---

0636. 函数的独占时间

• 标签：栈、数组
• 难度：中等

题目链接

• 0636. 函数的独占时间 - 力扣

题目大意

描述：

有一个单线程 CPU 正在运行一个含有 $n$ 道函数的程序。每道函数都有一个位于 $0$ 和 $n-1$ 之间的唯一标识符。

函数调用存储在一个「调用栈」上：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是 当前正在执行的函数。每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。

给定一个由日志组成的列表 $logs$，其中 $logs[i]$ 表示第 $i$ 条日志消息，该消息是一个按 "{function_id}:{"start" | "end"}:{timestamp}" 进行格式化的字符串。例如，"0:start:3" 意味着标识符为 $0$ 的函数调用在时间戳 $3$ 的起始开始执行；而 "1:end:2" 意味着标识符为 $1$ 的函数调用在时间戳 $2$ 的末尾结束执行。注意，函数可以调用多次，可能存在递归调用。

函数的「独占时间」定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 $2$ 单位时间，另一次调用执行 $1$ 单位时间，那么该函数的 独占时间 为 $2 + 1 = 3$。

要求：

以数组形式返回每个函数的「独占时间」，其中第 $i$ 个下标对应的值表示标识符 $i$ 的函数的独占时间。

说明：

• $1 \le n \le 10^{3}$。
• $2 \le logs.length \le 500$。
• $0 \le function_id \lt n$。
• $0 \le timestamp \le 10^{9}$。
• 两个开始事件不会在同一时间戳发生。
• 两个结束事件不会在同一时间戳发生。
• 每道函数都有一个对应 "start" 日志的 "end" 日志。

示例：

• 示例 1：

输入：n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
输出：[3,4]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，于时间戳 1 的末尾结束执行。 
函数 1 在时间戳 2 的起始开始执行，执行 4 个单位时间，于时间戳 5 的末尾结束执行。 
函数 0 在时间戳 6 的开始恢复执行，执行 1 个单位时间。 
所以函数 0 总共执行 2 + 1 = 3 个单位时间，函数 1 总共执行 4 个单位时间。

• 示例 2：

输入：n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
输出：[8]
解释：
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。
函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。
函数 0（初始调用）恢复执行，并立刻再次调用它自身。
函数 0（第二次递归调用）在时间戳 6 的起始开始执行，执行 1 个单位时间。
函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间。
所以函数 0 总共执行 2 + 4 + 1 + 1 = 8 个单位时间。

解题思路

思路 1：栈

这道题目需要模拟函数调用栈的执行过程，计算每个函数的独占时间。

1. 使用栈来模拟函数调用过程，栈中存储函数的 ID。
2. 使用数组 $ans$ 记录每个函数的独占时间。
3. 使用变量 $prev\underline{~}time$ 记录上一个时间戳。
4. 遍历日志列表：
   • 解析日志，获取函数 ID、操作类型（start/end）和时间戳。
   • 如果是 start 操作：
     • 如果栈不为空，说明有函数正在执行，将当前时间与上一个时间的差值累加到栈顶函数的独占时间中。
     • 将当前函数 ID 入栈。
     • 更新 $prev\underline{~}time$ 为当前时间戳。
   • 如果是 end 操作：
     • 将栈顶函数出栈，并将当前时间与上一个时间的差值加 1（因为 end 时刻也属于该函数）累加到该函数的独占时间中。
     • 更新 $prev\underline{~}time$ 为当前时间戳加 1。
5. 返回结果数组 $ans$。

思路 1：代码

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        ans = [0] * n  # 记录每个函数的独占时间
        stack = []  # 模拟函数调用栈
        prev_time = 0  # 记录上一个时间戳
        
        for log in logs:
            parts = log.split(':')
            func_id = int(parts[0])
            op_type = parts[1]
            timestamp = int(parts[2])
            
            if op_type == 'start':
                # 如果栈不为空，当前栈顶函数被暂停
                if stack:
                    ans[stack[-1]] += timestamp - prev_time
                # 当前函数入栈
                stack.append(func_id)
                prev_time = timestamp
            else:  # end
                # 当前函数出栈，累加独占时间
                func_id = stack.pop()
                ans[func_id] += timestamp - prev_time + 1
                prev_time = timestamp + 1
        
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(m)$，其中 $m$ 是日志的数量。需要遍历所有日志。
• 空间复杂度：$O(n)$，其中 $n$ 是函数的数量。需要使用栈来存储函数调用关系，最坏情况下所有函数都在栈中。