1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        Deque<int[]> functionStack = new ArrayDeque<>();
        int start = 0, end = 0;
        functionStack.push(new int[] { -1, 0 });
        int[] ans = new int[n];
        for (String log : logs) {
            String[] info = log.split(":");
            if (info[1].equals("start")) {
                end = Integer.parseInt(info[2]);
                functionStack.peek()[1] += end - start;
                int funcId = Integer.parseInt(info[0]);
                functionStack.push(new int[] { funcId, 0 });
                start = end;
            } else {
                end = Integer.parseInt(info[2]);
                int[] topFunc = functionStack.pop();
                ans[topFunc[0]] += topFunc[1] + end - start + 1;
                start = end + 1;
            }
        }
        return ans;
    }
}

我写的第一版答案, 思路就是记录start和end的时间, 如果遇到start的log, 我们计算上一段时间也就是end - start, 把它加到上一个func的运行时间上去然后把此时的func压入栈中. 如果遇到end, 那说明栈顶的func执行完毕, 我们把它pop出来然后把上一段运行时间加上它之前运行的时间放入array中. 这里我们要注意, array中对应的位置上可能本来就有值, 因为函数可能是递归的, 之前有返回的func在array的相应位置上记录了运行时间, 此时我们结束的func可能和之前的这个一样, 于是我们把array中的func的运行时间加上栈上记录的再加上上一段的(end - start + 1).

这里需要注意的是start时刻是包含在当前函数的运行时间内的, 因此下一个start的开始时间包含在下一个函数的运行时间内而非上一个函数的运行时间内, 因此是end - start, 此时我们更新start为end, 也就是下一个func开始的时间. end是包含在当前的运行时间内, start当然也是, 因此是end - start + 1. 此时我们更新start的时候就需要更新为end + 1而不是end了.

时间复杂度: O(n) n是log的长度.
空间复杂度: O(n) 我们要存每个func的运行时间.