题目链接：https://leetcode.cn/problems/exclusive-time-of-functions/
思路
方法一、栈
直接想法
题目的大致意思就是模拟程序用栈的方法来实现函数的调用，函数有编号，开始时间和结束时间，但是在这段时间内并不是只实行当前这个函数也可能会暂停去执行另一个函数或者递归本身，所以我们需要模拟栈来保存函数的编号和当前的开始时间或者是结束时间，来计算每个函数都执行了多少时间单元
算法
1.初始化一个存放函数编号和开始时间或结束时间的堆栈
2.遍历logs日志列表，判断是start还是end
1） 如果是start，我们需要判断上一个函数是否已经end执行完成，若没有则让上一个函数进入睡眠状态，等到后面end的时候进行唤醒，也就是把上一个函数的开始时间修改成当前函数的开始时间，再把当前函数的编号和开始时间添加到堆栈顶部，如果已经完成了，则把当前的函数编号和开始时间放入堆栈顶部
2）如果是end，我们需要判断是堆栈顶部的函数编号是否是我当前要结束的函数编号，如果是相同，则直接消除栈顶元素，记录函数执行的时间单元，若不是我们当前要结束的函数编号，我们需要拿出上一个函数结束时间当作，当前函数的开始时间来记录函数执行的时间单元
代码示例
func exclusiveTime(n int, logs []string) []int { ans := make([]int, n) type pair struct{ idx, timestamp int } st := []pair{} for _, log := range logs { sp := strings.Split(log, ":") idx, _ := strconv.Atoi(sp[0]) timestamp, _ := strconv.Atoi(sp[2]) if sp[1][0] == 's' { if len(st) > 0 { ans[st[len(st)-1].idx] += timestamp - st[len(st)-1].timestamp st[len(st)-1].timestamp = timestamp } st = append(st, pair{idx, timestamp}) } else { p := st[len(st)-1] st = st[:len(st)-1] ans[p.idx] += timestamp - p.timestamp + 1 if len(st) > 0 { st[len(st)-1].timestamp = timestamp + 1 } } } return ans }
复杂度分析
- 时间复杂度：O(n)，其中n表示是logs日志数组的长度，遍历一次logs日志数组需要O(n)的时间
- 空间复杂度：O(n)，我们需要额外申请长度为n的函数数组
