0636. Exclusive Time of Functions¶
题目信息¶
- 题号:
0636
- 难度:
Medium
- 主题:
单线程调用栈、开始结束日志、包含式时间、独占执行时长
- 原题:
- 重点:
函数可以嵌套或递归调用、结束时间戳对应的单位也计入执行、被子调用占用的时间不能计入调用者独占时长
题目重述¶
一个单线程 CPU 上有编号 0 到 n-1 的函数。给定按时间顺序排列的日志 logs,每条日志格式为 "id:start:timestamp" 或 "id:end:timestamp",记录一次函数调用的开始或结束。
函数调用可以嵌套,也可以递归调用同一个函数。开始日志表示函数在该时间单位起开始执行;结束日志表示函数在该时间单位结束后才退出,因此结束时间戳本身也属于该调用。返回长度为 n 的数组,其中第 i 项是所有编号为 i 的调用实际占用 CPU、且未被其子调用占用的总时间。n 位于 [1, 100],日志数量位于 [1, 500],输入保证调用栈结构合法。
自建示例¶
父调用被子调用暂停:
输入:n = 2,logs = ["0:start:1","1:start:3","1:end:5","0:end:6"]
输出:[3,3]
解释:函数 1 独占时间为 3、4、5;函数 0 在时间 1、2 和 6 执行,独占时间也是 3。
同一函数递归调用:
输入:n = 1,logs = ["0:start:0","0:start:2","0:end:3","0:end:5"]
输出:[6]
解释:虽然中间发生递归,但六个时间单位始终由编号 0 的某次调用占用,因此总独占时间为 6。