636. 函数的独占时间
题目描述
一个单线程 CPU 上运行着 n 个函数，编号为 0 到 n - 1。函数之间可以互相调用，也可以递归调用自己，同一个函数可以被调用多次。调用关系按栈来管理：函数开始时压栈，结束时出栈，任何时刻只有栈顶的函数在执行。
输入整数 n 和按时间先后排列的日志数组 logs。每条日志是形如 "编号:start:时间戳" 或 "编号:end:时间戳" 的字符串。start 表示该函数在这个时间单位的开头开始运行；end 表示它在这个时间单位的末尾结束，因此这个时间单位本身也算它的执行时间。
一个函数的独占时间，是它在所有调用中真正位于栈顶执行的时间之和，被它调用的其他函数运行的时间不计入。
返回长度为 n 的数组，下标 i 处是编号为 i 的函数的独占时间。
输入：n = 2 logs = ["0:start:0","1:start:2","1:end:5","0:end:6"] 输出：[3,4]
解释：函数 0 在时间 0 到 1 执行 2 个单位，函数 1 在时间 2 到 5 执行 4 个单位，函数 0 在时间 6 再执行 1 个单位，合计 [3,4]。
输入：n = 1 logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"] 输出：[8]
解释：函数 0 的初始调用共执行 2 + 1 = 3 个单位，两次递归调用分别执行 4 和 1 个单位，总计 8。
输入：n = 2 logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"] 输出：[7,1]
解释：函数 0 两次调用合计 2 + 4 + 1 = 7 个单位，函数 1 在时间 6 执行 1 个单位。
数据范围
1 <= n <= 1002 <= logs.length <= 5000 <= function_id < n0 <= timestamp <= 10^9- 不会有两个 start 事件出现在同一时间戳。
- 不会有两个 end 事件出现在同一时间戳。
- 每个函数的 start 日志都有与之配对的 end 日志。
解题思路
函数调用天然是栈结构：栈顶就是正在运行的函数。用 prev 记录“上一段时间从哪个时间单位开始”。遇到 start：从 prev 到 ts-1 这段时间属于当前栈顶，累加 ts - prev，然后新函数入栈，prev = ts。遇到 end：从 prev 到 ts（含）属于栈顶，累加 ts - prev + 1 并出栈，下一段从 ts+1 开始。
为什么正确
时间单位 0..prev-1 都已经计入某个函数；栈从底到顶是当前的调用链，栈顶正在运行。
复杂度分析
时间 O(m)，m 为日志条数；空间 O(m)（栈）。
易错点
start 的时间戳指时间单位的开头，end 的时间戳指时间单位的末尾，所以 end 要 +1，且之后 prev = ts + 1。同一个函数可以递归调用自己，累加到同一个 res 上即可。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res = [0] * n
stack = []
prev = 0
for log in logs:
fid, typ, ts = log.split(':')
fid, ts = int(fid), int(ts)
if typ == 'start':
if stack:
res[stack[-1]] += ts - prev
stack.append(fid)
prev = ts
else:
res[stack.pop()] += ts - prev + 1
prev = ts + 1
return resclass Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
int prev = 0;
for (String log : logs) {
String[] parts = log.split(":");
int fid = Integer.parseInt(parts[0]), ts = Integer.parseInt(parts[2]);
if (parts[1].equals("start")) {
if (!stack.isEmpty()) {
res[stack.peek()] += ts - prev;
}
stack.push(fid);
prev = ts;
} else {
res[stack.pop()] += ts - prev + 1;
prev = ts + 1;
}
}
return res;
}
}class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> res(n, 0);
vector<int> stack;
int prev = 0;
for (const string& log : logs) {
size_t p1 = log.find(':'), p2 = log.rfind(':');
string typ = log.substr(p1 + 1, p2 - p1 - 1);
int fid = stoi(log.substr(0, p1)), ts = stoi(log.substr(p2 + 1));
if (typ == "start") {
if (!stack.empty()) {
res[stack.back()] += ts - prev;
}
stack.push_back(fid);
prev = ts;
} else {
res[stack.back()] += ts - prev + 1;
stack.pop_back();
prev = ts + 1;
}
}
return res;
}
};func exclusiveTime(n int, logs []string) []int {
res := make([]int, n)
stack := []int{}
prev := 0
for _, log := range logs {
parts := strings.Split(log, ":")
fid, _ := strconv.Atoi(parts[0])
ts, _ := strconv.Atoi(parts[2])
if parts[1] == "start" {
if len(stack) > 0 {
res[stack[len(stack)-1]] += ts - prev
}
stack = append(stack, fid)
prev = ts
} else {
res[stack[len(stack)-1]] += ts - prev + 1
stack = stack[:len(stack)-1]
prev = ts + 1
}
}
return res
}var exclusiveTime = function(n, logs) {
const res = new Array(n).fill(0);
const stack = [];
let prev = 0;
for (const log of logs) {
const [f, typ, t] = log.split(':');
const fid = Number(f), ts = Number(t);
if (typ === 'start') {
if (stack.length) {
res[stack[stack.length - 1]] += ts - prev;
}
stack.push(fid);
prev = ts;
} else {
res[stack.pop()] += ts - prev + 1;
prev = ts + 1;
}
}
return res;
};function exclusiveTime(n: number, logs: string[]): number[] {
const res: number[] = new Array(n).fill(0);
const stack: number[] = [];
let prev = 0;
for (const log of logs) {
const [f, typ, t] = log.split(':');
const fid = Number(f), ts = Number(t);
if (typ === 'start') {
if (stack.length) {
res[stack[stack.length - 1]] += ts - prev;
}
stack.push(fid);
prev = ts;
} else {
res[stack.pop()!] += ts - prev + 1;
prev = ts + 1;
}
}
return res;
}