Exclusive Time of Functions

给一个单线程CPU和一个log, 求问每个thread自己独占CPU的时间. 这个题很tricky, 因为根本看不懂题目要求, 本来以为简单的线性扫描就可以了, 然后发现thread里有递归的出现,即: 同一个id连续start多次. 那么只能模拟栈了. 然后还需要注意的是, 因为是单线程, 所以不会出现两个线程重叠的情况, 即: 一个id end在另一个id start 和end中.

用stack的时候, 只放start time, 然后遇到end的时候, 计算time chunk. 因为end在time chunk之后, 所以要做差后+1. 另外, 还需要注意, 每当一个id end, 要看是否stack中有其他thread在等待, 这时候要在等待的id中减去当前的时间, 因为对于等待的id, 这段时间已经被当前id所占有.

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        Stack<int[]> stack = new Stack<>();
        int[] res = new int[n];
        for(String log : logs) {
            String[] strs = log.split(":");
            Integer id = Integer.valueOf(strs[0]);
            String opt = strs[1];
            Integer time = Integer.valueOf(strs[2]);
            if(opt.equals("start")) {
                stack.push(new int[]{id, time});
            } else {
                int[] prev = stack.pop();
                int diff = time - prev[1] + 1; // the time different
                res[id] += diff;
                if(!stack.isEmpty()) {
                    int[] p = stack.peek();
                    res[p[0]] -= diff; // use negative to mark the previous waiting thread
                }
            }
       }
        return res;
    }
}