题目
-
概述：给定n个函数的运行日志，让你给出每个函数的独占时间
独占时间不包括调用其他函数的时间
函数可能会被递归调用或被其它函数调用
-
输入：
函数数量n，范围[1, 100]
-
函数日志列表，格式为"function_id：start_or_end：timestamp"：
- function_id：函数ID，范围为[0, n-1]
- start_or_end：start或者end
- timestamp：函数开始时间或结束时间
输入日志会根据时间戳排序
两个函数不会在同时开始或结束
输出：按函数ID依次输出函数的独占时间
出处：https://leetcode-cn.com/problems/exclusive-time-of-functions/
思路
函数的调用系统就是用栈实现的，所以这里也使用栈
-
观察函数日志每一项：
- start_or_end为start => 直接入栈
- start_or_end为end => 弹出栈顶元素，计算函数经过时间并累加到对应ID的时间上，同时，让此时栈顶元素对应ID的时间减去当前的函数经过时间(如果栈顶有元素的话)
代码
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
LinkedList<MethodLog> stack = new LinkedList<>();
int[] result = new int[n];
Arrays.fill(result, 0);
String[] log;
int id;
boolean isStart;
int timeStamp;
MethodLog top;
int time;
for (String s : logs) {
log = s.split(":");
id = Integer.parseInt(log[0]);
isStart = "start".equals(log[1]);
timeStamp = Integer.parseInt(log[2]);
if (isStart) {
stack.push(new MethodLog(id, isStart, timeStamp));
} else {
top = stack.pop();
time = timeStamp - top.timeStamp + 1;
result[top.id] += time;
if (!stack.isEmpty()) {
result[stack.peek().id] -= time;
}
}
}
return result;
}
private class MethodLog {
int id;
boolean isStart;
int timeStamp;
MethodLog(int id, boolean isStart, int timeStamp) {
this.id = id;
this.isStart = isStart;
this.timeStamp = timeStamp;
}
}
}
