Medium

题目描述

在单线程 CPU 上，我们执行一个包含 n 个函数的程序。每个函数都有一个 0 到 n-1 之间的唯一 ID。

函数调用存储在调用栈中：当函数调用开始时，其 ID 被推入栈中，当函数调用结束时，其 ID 从栈中弹出。栈顶的函数 ID 是当前正在执行的函数。每当函数开始或结束时，我们都会写一个包含 ID、开始或结束状态以及时间戳的日志。

给你一个日志列表 logs，其中 logs[i] 表示第 i 条日志消息，格式为字符串 “{function_id}:{“start” | “end”}:{timestamp}"。例如，“0:start:3” 表示函数 ID 为 0 的函数调用在时间戳 3 的开始时刻开始，“1:end:2” 表示函数 ID 为 1 的函数调用在时间戳 2 的结束时刻结束。注意，函数可能会被多次调用，甚至递归调用。

函数的独占时间是程序中该函数所有调用的执行时间总和。例如，如果一个函数被调用两次，一次执行 2 个时间单位，另一次执行 1 个时间单位，则独占时间为 2 + 1 = 3。

返回每个函数的独占时间数组，其中第 i 个索引处的值表示 ID 为 i 的函数的独占时间。

示例 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：

输入：n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
输出：[8]

示例 3：

输入：n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]
输出：[7,1]

提示：

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

解题思路

这道题需要模拟函数调用栈的执行过程，计算每个函数的独占执行时间。

核心思路：

  1. 使用栈来模拟函数调用栈，栈中存储函数ID
  2. 遍历日志，根据start/end事件更新函数执行时间
  3. 关键在于理解"独占时间"的含义：函数执行时间 = 总时间 - 被其他函数占用的时间

具体算法：

  1. 维护一个栈存储正在执行的函数ID
  2. 对于start事件：
    • 如果栈不为空，说明当前栈顶函数被暂停，需要累加其执行时间
    • 将新函数ID入栈，记录开始时间
  3. 对于end事件：
    • 计算当前函数的执行时间并累加
    • 将函数ID出栈
    • 更新时间戳为下一个时间点（因为end表示在该时间戳结束）

时间复杂度分析：

  • 需要遍历所有日志，每个日志的处理时间为O(1)
  • 解析字符串的时间也是常数时间
  • 总时间复杂度为O(m)，其中m是日志数量

空间复杂度：

  • 栈的最大深度不会超过n（函数数量）
  • 结果数组需要O(n)空间
  • 总空间复杂度为O(n)

代码实现

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> result(n, 0);
        stack<int> st;
        int prevTime = 0;
        
        for (const string& log : logs) {
            int colon1 = log.find(':');
            int colon2 = log.find(':', colon1 + 1);
            
            int funcId = stoi(log.substr(0, colon1));
            string action = log.substr(colon1 + 1, colon2 - colon1 - 1);
            int timestamp = stoi(log.substr(colon2 + 1));
            
            if (action == "start") {
                if (!st.empty()) {
                    result[st.top()] += timestamp - prevTime;
                }
                st.push(funcId);
                prevTime = timestamp;
            } else {
                result[st.top()] += timestamp - prevTime + 1;
                st.pop();
                prevTime = timestamp + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        result = [0] * n
        stack = []
        prev_time = 0
        
        for log in logs:
            parts = log.split(':')
            func_id = int(parts[0])
            action = parts[1]
            timestamp = int(parts[2])
            
            if action == "start":
                if stack:
                    result[stack[-1]] += timestamp - prev_time
                stack.append(func_id)
                prev_time = timestamp
            else:
                result[stack[-1]] += timestamp - prev_time + 1
                stack.pop()
                prev_time = timestamp + 1
        
        return result

public class Solution {
    public int[] ExclusiveTime(int n, IList<string> logs) {
        int[] result = new int[n];
        Stack<int> stack = new Stack<int>();
        int prevTime = 0;
        
        foreach (string log in logs) {
            string[] parts = log.Split(':');
            int funcId = int.Parse(parts[0]);
            string action = parts[1];
            int timestamp = int.Parse(parts[2]);
            
            if (action == "start") {
                if (stack.Count > 0) {
                    result[stack.Peek()] += timestamp - prevTime;
                }
                stack.Push(funcId);
                prevTime = timestamp;
            } else {
                result[stack.Peek()] += timestamp - prevTime + 1;
                stack.Pop();
                prevTime = timestamp + 1;
            }
        }
        
        return result;
    }
}

var exclusiveTime = function(n, logs) {
    const result = new Array(n).fill(0);
    const stack = [];
    let prevTime = 0;
    
    for (const log of logs) {
        const [id, action, time] = log.split(':');
        const funcId = parseInt(id);
        const timestamp = parseInt(time);
        
        if (action === 'start') {
            if (stack.length > 0) {
                result[stack[stack.length - 1]] += timestamp - prevTime;
            }
            stack.push(funcId);
            prevTime = timestamp;
        } else {
            result[stack.pop()] += timestamp - prevTime + 1;
            prevTime = timestamp + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m)，其中 m 是日志数量，需要遍历所有日志
空间复杂度O(n)，其中 n 是函数数量，栈的最大深度为 n，结果数组大小为 n