栈题目：函数的独占时间

题目

标题和出处

标题：函数的独占时间

出处：636. 函数的独占时间

难度

6 级

题目描述

要求

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

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

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

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：$\text{n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"]}$
输出：$\text{[8,1]}$

示例 5：

输入：$\text{n = 1, logs = ["0:start:0","0:end:0"]}$
输出：$\text{[1]}$

数据范围

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

解法

思路和算法

由于函数调用的方式是存储在调用栈上，因此可以使用栈模拟函数的调用，栈顶元素表示正在执行的函数的标识符。

对于给定的日志列表，其存储顺序为按照时间戳的顺序，因此可以遍历日志列表，计算每个函数的独占时间。每条日志包含三项信息，分别是：函数标识符、开始还是结束、时间戳。计算函数独占时间时，需要考虑当前时间戳和上一个时间戳，以及需要考虑以下不同的情况：

• 函数开始执行，且栈为空，此时没有其他函数正在执行，因此不需要更新任何函数的独占时间，将当前函数标识符入栈；

• 函数开始执行，且栈不为空，此时栈顶标识符对应的原函数正在执行，新函数开始执行之后的时间不计入原函数的独占时间，因此需要更新原函数的独占时间，将当前时间戳和上一个时间戳之差加到原函数的独占时间，然后将当前函数标识符入栈；

• 函数结束执行，由于当前时间戳表示时间戳的末尾，因此需要将时间戳加 $1$，此时栈顶的标识符和当前函数标识符一定相同，当前函数的最近一段独占时间即为当前时间戳（已经加 $1$）和上一个时间戳之差，将当前时间戳和上一个时间戳之差加到当前函数的独占时间，并将栈顶元素出栈，栈顶元素出栈后如果栈不为空，则新的栈顶元素为恢复独占时间的原函数。

对一条日志处理结束之后，将当前时间戳存为上一个时间戳，然后处理下一条日志，直到全部日志处理完毕，即可得到每个函数的独占时间。

示例 3 的函数的独占时间如下图所示。

函数的独占时间计算过程如下。初始时 $\text{time}=[0,0]$。

$[\text{0:start:0}]$：函数标识符 $\text{id}=0$，时间戳 $\text{timestamp}=0$，将 $0$ 入栈，$\text{time}=[0,0]$；

$[\text{0:start:2}]$：函数标识符 $\text{id}=0$，时间戳 $\text{timestamp}=2$，将 $2-0=2$ 加到 $\text{time}[0]$，将 $0$ 入栈，$\text{time}=[2,0]$；

$[\text{0:end:5}]$：函数标识符 $\text{id}=0$，时间戳 $\text{timestamp}=5+1=6$，将 $6-2=4$ 加到 $\text{time}[0]$，将 $0$ 出栈，$\text{time}=[6,0]$；

$[\text{1:start:6}]$：函数标识符 $\text{id}=1$，时间戳 $\text{timestamp}=6$，将 $6-6=0$ 加到 $\text{time}[0]$，将 $1$ 入栈，$\text{time}=[6,0]$；

$[\text{1:end:6}]$：函数标识符 $\text{id}=1$，时间戳 $\text{timestamp}=6+1=7$，将 $7-6=1$ 加到 $\text{time}[1]$，将 $1$ 出栈，$\text{time}=[6,1]$；

$[\text{0:end:7}]$：函数标识符 $\text{id}=0$，时间戳 $\text{timestamp}=7+1=8$，将 $8-7=1$ 加到 $\text{time}[0]$，将 $0$ 出栈，$\text{time}=[7,1]$。

代码

class Solution {
    
    public int[] exclusiveTime(int n, List<String> logs) {
    
        int[] time = new int[n];
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int prevTimestamp = 0;
        int size = logs.size();
        for (int i = 0; i < size; i++) {
    
            String log = logs.get(i);
            String[] logArray = log.split(":");
            int id = Integer.parseInt(logArray[0]);
            String action = logArray[1];
            int timestamp = Integer.parseInt(logArray[2]);
            if ("start".equals(action)) {
    
                if (!stack.isEmpty()) {
    
                    int prevId = stack.peek();
                    time[prevId] += timestamp - prevTimestamp;
                }
                stack.push(id);
            } else if ("end".equals(action)) {
    
                timestamp++;
                time[id] += timestamp - prevTimestamp;
                stack.pop();
            }
            prevTimestamp = timestamp;
        }
        return time;
    }
}

复杂度分析

• 时间复杂度：$O(m)$，其中 $m$ 是日志列表 $\text{logs}$ 的长度。需要遍历日志列表一次，对于每条日志的操作时间都是 $O(1)$。

• 空间复杂度：$O(m)$，其中 $m$ 是日志列表 $\text{logs}$ 的长度。空间复杂度主要取决于栈空间，栈存储被调用的函数，栈内元素个数不超过 $\frac{m}{2}$。返回值不计入空间复杂度。