leetcode 636. Exclusive Time of Functions | 636. 函数的独占时间（Stack）

墨蓝 2022-09-15 11:56 15阅读 0赞

## 题目 ##

[https://leetcode.com/problems/exclusive-time-of-functions/][https_leetcode.com_problems_exclusive-time-of-functions]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

类似于括号匹配问题，遍历 list，每一次来到新元素时，结算当前正在执行的函数已经运行的时间，累加到 result 数组的对应位置中。怎么知道当前正在执行哪个函数呢？维护函数调用栈即可，栈顶的元素就是正在执行的函数。

需要像括号匹配那样维护函数调用栈，即当遇到相同元素的 end 时，想象成括号闭合，则 pop 栈顶元素；如果不能闭合，则将当前看到的元素入栈。

需要注意的细节：start 时间点和 end 时间点的开闭区间不一样。

class Solution { 
        public static final int ID = 0;
        public static final int STATUS = 1;
        public static final int TIMESTAMP = 2;
        public static final String START = "start";
        public static final String END = "end";
    
        public int[] exclusiveTime(int n, List<String> logs) { 
            Stack<Integer> stack = new Stack<>(); // call stack (id)
            int[] result = new int[n];
            for (int i = 0; i < logs.size(); i++) { 
                boolean paired = false;
                String[] curLog = logs.get(i).split(":");
                if (!stack.isEmpty()) { 
                    String[] preLog = logs.get(i - 1).split(":");
                    Integer runningId = stack.peek();
    
                    int diff = Integer.parseInt(curLog[TIMESTAMP]) - Integer.parseInt(preLog[TIMESTAMP]);
                    if (preLog[STATUS].equals(START) && curLog[STATUS].equals(END)) diff += 1;
                    if (preLog[STATUS].equals(END) && curLog[STATUS].equals(START)) diff -= 1;
                    result[runningId] += diff;
    
                    if (curLog[STATUS].equals(END) && Integer.parseInt(curLog[ID]) == runningId) {  // 成功匹配
                        stack.pop();
                        paired = true;
                    }
                }
                if (!paired) stack.push(Integer.parseInt(curLog[ID]));
            }
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_exclusive-time-of-functions]: https://leetcode.com/problems/exclusive-time-of-functions/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/16b93f616aa84b168592a48b9c1ccf56.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8b7e4b752e90462cbd505ba4d2e821bd.png