题目

• 概述：给定n个函数的运行日志，让你给出每个函数的独占时间

  独占时间不包括调用其他函数的时间

  函数可能会被递归调用或被其它函数调用

• 输入：

  1. 函数数量n，范围[1, 100]

  2. 函数日志列表，格式为"function_id：start_or_end：timestamp"：

     1. function_id：函数ID，范围为[0, n-1]
     2. start_or_end：start或者end
     3. timestamp：函数开始时间或结束时间

     输入日志会根据时间戳排序

     两个函数不会在同时开始或结束

• 输出：按函数ID依次输出函数的独占时间

• 出处：https://leetcode-cn.com/problems/exclusive-time-of-functions/

思路

• 函数的调用系统就是用栈实现的，所以这里也使用栈

• 观察函数日志每一项：

  1. start_or_end为start => 直接入栈
  2. start_or_end为end => 弹出栈顶元素，计算函数经过时间并累加到对应ID的时间上，同时，让此时栈顶元素对应ID的时间减去当前的函数经过时间(如果栈顶有元素的话)

代码

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        LinkedList<MethodLog> stack = new LinkedList<>();
        int[] result = new int[n];
        Arrays.fill(result, 0);
        
        String[] log;
        int id;
        boolean isStart;
        int timeStamp;
        MethodLog top;
        int time;
        for (String s : logs) {
            log = s.split(":");
            id = Integer.parseInt(log[0]);
            isStart = "start".equals(log[1]);
            timeStamp = Integer.parseInt(log[2]);
            if (isStart) {
                stack.push(new MethodLog(id, isStart, timeStamp));
            } else {
                top = stack.pop();
                time = timeStamp - top.timeStamp + 1;
                result[top.id] += time;
                if (!stack.isEmpty()) {
                    result[stack.peek().id] -= time;
                }
            }
        }
        
        return result;
    }
    
    private class MethodLog {
        int id;
        boolean isStart;
        int timeStamp;
        
        MethodLog(int id, boolean isStart, int timeStamp) {
            this.id = id;
            this.isStart = isStart;
            this.timeStamp = timeStamp;
        }
    }
}