题目描述

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

函数调用存储在一个调用栈上：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是当前正在执行的函数。

每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。给你一个由日志组成的列表 logs，请你返回每个函数的独占时间。

每条日志的格式为 "function_id:start|end:timestamp"，其中 timestamp 是一个非负整数，表示函数开始或结束的时间点。注意，同一个函数可能会被递归调用多次。

“独占时间” 是指该函数在 CPU 上执行的所有时间片段之和，不包括它调用其他函数所花费的时间。

解题思路

本题的核心是模拟调用栈来跟踪当前正在执行的函数，并记录每个时间片段归谁所有。

关键点：时间片的含义

时间戳表示某个时刻，函数从 timestamp 开始执行，或恰好在 timestamp 结束。举例来说：

  • 0:start:2 表示函数 0 在时刻 2 开始
  • 0:end:5 表示函数 0 在时刻 5 结束

那么函数 0 一共运行了 5 - 2 + 1 = 4 个单位时间（即时刻 2、3、4、5）。

算法步骤

维护一个栈 stack、一个结果数组 res，和一个变量 prevTime 记录上一个事件发生的时间点。

  1. 遍历每一条日志，解析出 function_id、op（start 或 end）、time。

  2. 遇到 start 日志：

    • 如果栈不为空，说明栈顶函数在 [prevTime, time-1] 这段时间内正在运行，将这 time - prevTime 的时间加到该函数的独占时间中。
    • 将新函数入栈，并更新 prevTime = time。

  3. 遇到 end 日志：

    • 弹出栈顶函数，该函数在当前栈顶期间运行了 [prevTime, time] 这段时间（注意包含结束时刻），所以独占时间加上 time - prevTime + 1。
    • 更新 prevTime = time + 1，因为时刻 time + 1 开始由新的栈顶函数（如果有的话）占用。

为什么这样计算是正确的？

关键在于 prevTime 的维护：每次事件发生时，我们结算上一个事件到当前事件之间 CPU 被谁占用。start 事件不包含当前时刻（当前时刻开始由新函数占用），而 end 事件包含当前时刻（函数恰好在此时刻结束），所以计算方式不同。

通过栈来追踪函数的嵌套关系，每次只是把时间片段分给栈顶函数——因为单线程 CPU 同一时刻只有一个函数在执行，而它一定是调用栈最顶端的那个函数。

复杂度分析

  • 时间复杂度：O(m)，其中 m 是日志数量。我们只需要遍历一遍所有日志，每次日志的处理都是 O(1) 的栈操作。
  • 空间复杂度：O(n)，其中 n 是函数数量。需要一个大小为 n 的结果数组来存储每个函数的独占时间，以及一个调用栈，最坏情况下所有函数都在调用栈中，空间为 O(n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package code.J636;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class J636 {
    public int[] exclusiveTime(int n, List<String> logs) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[n];
        int prevTime = 0;
        for (String str : logs) {
            String[] split = str.split(":");
            int function_id = Integer.parseInt(split[0]);
            String op = split[1];
            int time = Integer.parseInt(split[2]);
            if (op.equals("start")) {
                if (!deque.isEmpty()) {
                    res[deque.peek()] += time - prevTime;
                }
                deque.push(function_id);
                prevTime = time;
            }
            if (op.equals("end")) {
                res[deque.pop()] += time - prevTime + 1;
                prevTime = time + 1;
            }
        }
        return res;
    }
}