Leetcode 636. 函数的独占时间

题目

给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。

每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。

日志是具有以下格式的字符串：function_id：start_or_end：timestamp。例如：“0:start:0” 表示函数 0 从 0 时刻开始运行。“0🔚0” 表示函数 0 在 0 时刻结束。

函数的独占时间定义是在该方法中花费的时间，调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。

示例:

输入:
n = 2
logs = 
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
输出:[3, 4]
说明：
函数 0 在时刻 0 开始，在执行了  2个时间单位结束于时刻 1。
现在函数 0 调用函数 1，函数 1 在时刻 2 开始，执行 4 个时间单位后结束于时刻 5。
函数 0 再次在时刻 6 开始执行，并在时刻 6 结束运行，从而执行了 1 个时间单位。
所以函数 0 总共的执行了 2 +1 =3 个时间单位，函数 1 总共执行了 4 个时间单位。

说明：

1. 输入的日志会根据时间戳排序，而不是根据日志Id排序。
2. 你的输出会根据函数Id排序，也就意味着你的输出数组中序号为 0 的元素相当于函数0 的执行时间。
3. 两个函数不会在同时开始或结束。
4. 函数允许被递归调用，直到运行结束。
5. 1 <= n <= 100

题解

栈应用。
对于start，我们push id及time；对于end，我们需要pop，同时记录其独占时间，需要注意一点的时，这期间可能有别的线程运行，因此并不是简单的通过字符串给定的结束时间和开始时间，如果栈中有线程，我们只需要将栈顶的时间-当前pop的线程的起止时间。详细过程见代码

代码

	vector<int> exclusiveTime(int n, vector<string>& logs) {
        stack<pair<int,int>> sp;
        vector<int> ans(n,0);
        int size = logs.size(),time;
        for(int i=0; i<size; i++){
            int id,j,now;
            for(j=0; j<logs[i].length(); j++)
                if(logs[i][j] == ':')  break;
            id = stoi(logs[i].substr(0,j));
            j++;
            if(logs[i][j] == 's'){		//start线程，push id和time
                while(logs[i][j] != ':')    j++;
                now = stoi(logs[i].substr(j+1));
                sp.push(make_pair(id,now));
            }else{				//end线程，
                while(logs[i][j] != ':')    j++;
                now = stoi(logs[i].substr(j+1));		//获取当前pop线程的终止时间
                time = now-sp.top().second+1;			
                ans[sp.top().first] += time;
                sp.pop();
                if(!sp.empty())				//栈顶有线程，将时间要-调用的线程的起止时间
                    ans[sp.top().first] -= time;
            }
        }
        return ans;
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/exclusive-time-of-functions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。