636函数独占时间

下面是题目给出的模板

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {

    }
};

思路

首先要明白，这是一个非抢占单线程CPU，也就是说每次只能执行一个函数，所以当第一个函数调用第二个函数之后，第一个函数就暂停执行了，只有当第二个函数执行完毕，才能会过来执行第一个函数

所以，我们自然可以用栈来模拟这个过程了

当一个函数开始的时候，入栈，所以多个函数调用的时候，栈顶就是当下正在运行的函数。

那么我们得到一个end命令的时候，很显然肯定是和栈顶元素匹配的，那么我们就计算出来这个栈顶函数运行的时间了

但是这还没完，如果栈非空，那么当下一个end命令的时候，如果不做些什么，那么计算得到的时间就包含了他调用的那个函数的执行时间，而事实上应该是 结束时的时间减去该函数的开始时间再减去中间调用函数的时间

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> result(n, 0);
        stack<pair<int, int>> stk;
        for (string &log : logs) {
            //这里对字符串进行一个切割操作
            size_t pos1 = log.find(':');
            size_t pos2 = log.rfind(':');
            //这里通过stoi，得到这个函数的序号
            int currId = stoi(log.substr(0, pos1));
            //这里通过substr，得到了日志到底是start还是end
            string currAction = log.substr(pos1+1, pos2-pos1-1);
            //这里得到了函数开始或结束的时间
            int currTimestamp = stoi(log.substr(pos2+1));
            //那么如果等于开始的话。就入栈
            if (currAction == "start") {
                stk.push(make_pair(currId, currTimestamp));
            } else {
                //否则，我们先计算栈顶的函数的执行时间
                int duration = currTimestamp - stk.top().second + 1;
                result[currId] += duration;
                stk.pop();
                //如果占非空，那么就要把占里面的函数的独占时间减去刚才计算的函数运行的时间
                //因为那些时间不是这些栈里面的函数的独占时间！
                if (!stk.empty()) {
                    result[stk.top().first] -= duration;
                }
            }
        }
        return result;
    }
};