链接：https://leetcode.cn/problems/exclusive-time-of-functions/solution/by-xun-ge-v-qr29/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
由于本题是单线程CPU，一个任务进栈必然最终会由对应的该任务出栈结束。
我们只需要能在任务出栈的时候统计它和进栈的时候的时间差即可。
注意到期间可能在处理别的任务，所以我们需要排除掉其他任务的时间。
比较简单的做法是统计一个独立任务时间的总和，并在进栈的时候加入当时的总和。
那么出栈计算的时候减去中间被占用的独立时间就好了。

具体实现

我们可以用栈来模拟函数调用的过程，栈顶的元素为当前正在执行函数：

• 当函数调用开始时，如果当前有函数正在运行，则当前正在运行函数应当停止，此时计算其的执行时间，然后将调用函数入栈。
• 当函数调用结束时，将栈顶元素弹出，并计算相应的执行时间，如果此时栈顶有被暂停的函数，则开始运行该函数。

由于每一个函数都有一个对应的 start 和 end 日志，且当遇到一个 end 日志时，栈顶元素一定为其对应的start 日志。那么我们对于每一个函数记录它的函数标识符和上次开始运行的时间戳，此时我们只需要在每次函数暂停运行的时候来计算执行时间和开始运行的时候更新时间戳即可。

代码

typedef struct {
    int idx;
    int timestamp;//总共运行时间
} Pair;

int* exclusiveTime(int n, char ** logs, int logsSize, int* returnSize) {
    Pair *stack = (Pair *)malloc(sizeof(Pair)* logsSize); // {idx, 开始运行的时间}
    int *res = (int *)malloc(sizeof(int) * n);
    memset(res, 0, sizeof(int) * n);
    int top = 0;
    for (int i = 0; i < logsSize; i++) {
        char type[10];
        int idx, timestamp;
        sscanf(logs[i], "%d:%[^:]:%d", &idx, type, &timestamp);
        if (type[0] == 's') {//区分开始和结束
            if (top > 0) {//统计时间并保存，之前正在运行的程序
                res[stack[top - 1].idx] += timestamp - stack[top - 1].timestamp;
                stack[top - 1].timestamp = timestamp;
            }
            stack[top].idx = idx;//当前程序入栈运行
            stack[top].timestamp = timestamp;
            top++;
        } else {//结束当前运行程序
            res[stack[top - 1].idx] += timestamp - stack[top - 1].timestamp + 1;
            top--;
            if (top > 0) {
                stack[top - 1].timestamp = timestamp + 1;
            }
        }
    }
    free(stack);
    *returnSize = n;
    return res;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/exclusive-time-of-functions/solution/by-xun-ge-v-qr29/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。