一、题目

有一个 单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于 0 和 n-1 之间的唯一标识符。

函数调用 存储在一个 调用栈 上 ：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是当前正在执行的函数 。每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。

给你一个由日志组成的列表 logs ，其中 logs[i] 表示第 i 条日志消息，该消息是一个按 "{function_id}:{"start" | "end"}:{timestamp}" 进行格式化的字符串。例如，"0:start:3" 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ；而 "1:end:2" 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意，函数可以调用多次，可能存在递归调用 。

函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 2 单位时间，另一次调用执行 1 单位时间，那么该函数的 独占时间 为 2 + 1 = 3 。

以数组形式返回每个函数的 独占时间 ，其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。

二、示例

2.1> 示例 1：

【输入】n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
【输出】[3,4]
【解释】
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，于时间戳 1 的末尾结束执行。
函数 1 在时间戳 2 的起始开始执行，执行 4 个单位时间，于时间戳 5 的末尾结束执行。
函数 0 在时间戳 6 的开始恢复执行，执行 1 个单位时间。
所以函数 0 总共执行 2 + 1 = 3 个单位时间，函数 1 总共执行 4 个单位时间。

2.2> 示例 2：

【输入】n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
【输出】[8]
【解释】
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。
函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。
函数 0（初始调用）恢复执行，并立刻再次调用它自身。
函数 0（第二次递归调用）在时间戳 6 的起始开始执行，执行 1 个单位时间。
函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间。
所以函数 0 总共执行 2 + 4 + 1 + 1 = 8 个单位时间。

2.3> 示例 3：

【输入】n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
【输出】[7,1]
【解释】
函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。
函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。
函数 0（初始调用）恢复执行，并立刻调用函数 1 。
函数 1在时间戳 6 的起始开始执行，执行 1 个单位时间，于时间戳 6 的末尾结束执行。
函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间，于时间戳 7 的末尾结束执行。
所以函数 0 总共执行 2 + 4 + 1 = 7 个单位时间，函数 1 总共执行 1 个单位时间。

提示：

• 1 <= n <= 100
• 1 <= logs.length <= 500
• 0 <= function_id < n
• 0 <= timestamp <= 10^9
• 两个开始/结束事件不会在同一时间戳发生
• 每道函数都有一个对应 "start" 日志的 "end" 日志

三、解题思路

3.1> 思路1：堆栈 + current指针

通过题意，我们很容易想到java虚拟机中栈帧那一章节，针对不同方法的调用，都是通过调用方法进行入栈，执行完毕进行出栈的一系列操作。那么，既然我们想到了栈帧，那么，针对这道题的解题思路，也会很容易就联想到采用堆栈的方式进行逻辑控制和计算。

比如，我们通过入参的logs中，获得了方法a()开始执行，那么我们就将方法a()的start放入到堆栈中；那么此时方法b()也开始执行，那么同样的，我们再将方法b()的start放入到堆栈中。当此时方法b()执行完毕后，那么方法b()的start和方法b()的end配对成功，则将方法b()的start执行出栈操作。那么此时，堆栈中只剩下方法a()的start了，那么当方法a()执行完毕后，方法a()的start和方法a()的end配对成功，那么将方法a()的start执行出栈操作即可。此时堆栈中是空的了。也说明此时没有任何正在执行中的方法了。

既然算法设计的数据存储结构我们确定好了，那么如何进行方法执行时间的计算呢？其实，如果对于这种先调用方法a()的start，紧接着就调用了方法a()的end，这种情况来说，计算方法执行时间非常简单，即：end的时间戳减去start的时间戳再加1即可。但是，如果是方法嵌套调用，这个就会比较麻烦，比如：调用方法a()的start，调用方法b()的start，调用方法c()的start，调用方法c()的end，调用方法b()的end，调用方法a()的end。这么操作过程中，除了方法c()之外，其他方法调用耗时都不是end-start+1了。

那针对这种嵌套操作的调用关系，由于某些方法被中断暂停导致耗时不是连续的，而是割裂的。那么，如何计算其耗时呢？这里我们采用“今朝有酒今朝醉”的方式。什么意思呢？我们下面以一个例子作为切入点，来演示一下什么叫做今朝有酒今朝醉，这样会比纯文字叙述更容易让大家理解。

输入n=2，logs=["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"]，下面就是其执行时间的图示：

从logs获得第一个指令日志“0:start:0”，由于是第一个指令，则放入到堆栈中。此时的current指针用于指向“未参加计算”的起始位置。具体操作如下所示：

获得第二个指令日志“0:start:2”，由于还是start指令，所以，将其放入到堆栈中。但是此时由于又执行了start操作，所以第一个指令其实是处于暂停状态了，由于我们采用“今朝有酒今朝醉”的方式。所以，计算一下暂停前执行的耗时，并维护到result结果数组中；第二个start指令的时间戳是2，所以第一个指令执行了2个时间单位然后被暂停了。此时result数组中，index=0的元素被赋值为2。由于current指针指向的是未参加计算的起始位置，所以current被赋值为2。具体操作如下所示：

获得第三个指令日志“0:end:5”，由于是end指令，所以，从堆栈中pop弹出的栈顶元素一定就是其start指令的匹配指令。既然指令已经配对了，那么就可以计算start指令与end指令消耗的时间单位了。由于start指令是“0:start:2”，所以指令消耗的时间是5-2+1等于4，将result数组index等于0的元素加4，即：2+4等于6，current同被赋值为6。

当接收到指令“1:start:7”的时候，我们相当于又将“0:start:0”的方法执行了暂停，由于current=6，所以那么再执行暂停前“0:start:0”的方法运行了1个时间单位，更新result数组index=0处元素值加1，并将current赋值为7。

当接收到“1:end:7”时，我们可以计算出函数1的耗时单位为1，那么更新result数组index=1处元素值为1，并将current赋值为8。

最后，当我们接收到最后一个日志指令“0:end:8”时，它其实就是针对我们第一个日志指令“0:start:0”的结束标识。由于此时current=8，而end的时间单元也是8，所以执行时间为1单元，更新result数组index=0处的元素值加1，即总的加和过程为：2+4+1+1=8

通过对log指令日志的遍历计算，最终result数组中，指令0（index=0）耗时8个时间单元；指令1（index=1）耗时1个时间单元；

四、代码实现

4.1> 实现1：堆栈 + current指针

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int current = 0;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque(); 
        for (String log : logs) {
            String[] logArray = log.split(":");
            int endTime = Integer.valueOf(logArray[2]);
            if (logArray[1].equals("start")) {
                if (!stack.isEmpty()) {
                    result[stack.peek()] += endTime - current; 
                    current = endTime ;
                } 
                stack.push(Integer.valueOf(logArray[0]));
            } else {
                result[stack.pop()] += endTime - current + 1;
                current = endTime + 1;
            }
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」