Exclusive Time of Functions

follow up: also calculate inclusive time

What are Exclusive and Inclusive?!MicrosoftLearn

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Input:
n = 2
logs = 
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1. 
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time. 
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

1. Input logs will be sorted by timestamp, NOT log id.

2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.

3. Two functions won't start or end at the same time.

4. Functions could be called recursively, and will always end.

5. 1 <= n <= 100

利用stack，因为可以递归调用函数，所以一个函数可能会被调用多次，所以stack比较合适

在有新的start开始时，之前一个函数的用时就是start的时间，减去前一个的时间，因为是从0开始，所以不用加1，比如 0 start at 0， 然后1 start at 2， 所以0 -> 1运行的时间是2-0 = 2， 这里用prev来记录前一个的时间。 如果遇到end的时候，比如1start at 2， end at4，那么他的运行时间就是 4-2+1 = 3， 因为是2，3，4, prev这个时候不能设为4了，因为4是属于已经pop出去的那个函数的，下个函数是从4+1开始，所以prev要在之前函数end的时间的基础上加上1

时间复杂度 o(N) N 是log的size

.空间复杂度， The stack can grow up to a depth of at most n/2. Here, n refers to the number of elements in the given logs list.

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        Stack<Integer> stack = new Stack<>();
        
        String[] s = logs.get(0).split(":");
        
        stack.push(Integer.parseInt(s[0]));
        
        int prev = Integer.parseInt(s[2]);
        int i = 1;
        
        int[] res = new int[n];
        while(i < logs.size()){
            s = logs.get(i).split(":");
            
            if(s[1].equals("start")){
                if(!stack.isEmpty()){
                    res[stack.peek()] += Integer.parseInt(s[2] )- prev;
                }
                
                stack.push(Integer.parseInt(s[0]));
                prev = Integer.parseInt(s[2] );
            }else{
                res[stack.peek()] += Integer.parseInt(s[2] )- prev + 1;
                stack.pop();
                prev = Integer.parseInt(s[2] ) + 1;
            }
            i++;
        }
        
        return res;
    }
}

犯错，while循环条件里不用check stack是不是空，在调用peek的时候check就好