636. Exclusive Time of Functions

stack类似括号匹配O(n) time O(n) space

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n);
        stack<vector<int>> s;
        for (const auto &l : logs) {
            auto e = parse(l);
            if (e[1]) {
                int t = e[2] - s.top()[2] + 1; // 先计算最近一个线程的时间
                res[e[0]] += t; // 修改最近一个线程的时间
                s.pop();
                if (!s.empty()) { // 如果前面还有别的线程被阻塞
                    res[s.top()[0]] -= t; // 从那个线程上减去最近这个线程的运行时间
                    // s.top()[2] += t; 是错的因为只考虑了局部，这道题必须从全局考虑，所以应该直接处理对应线程的最终结果，两层以上的nested call就是错的
                }
            } else {
                s.push(e);
            }
        }
        return res;
    }

    vector<int> parse(const string &s) {
        int p1 = s.find(":"), p2 = s.find(":", p1 + 1);
        return {stoi(s.substr(0, p1)), s.substr(p1 + 1, p2 - p1 - 1) == "end", stoi(s.substr(p2 + 1))};
    }
};

class Solution {
    struct Log {
        Log(const string &s) {
            istringstream input(s);
            string token;
            getline(input, token, ':');
            id = stoi(token);
            getline(input, e, ':');
            getline(input, token, ':');
            time = stoi(token);
        }
        int id;
        string e;
        int time;
    };
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n);
        int sz = logs.size();
        stack<Log> s;
        for (const auto &log : logs) {
            Log curr(log);
            if (curr.e == "start") {
                s.push(curr);
            } else {
                Log prev = s.top();
                s.pop();
                int interval = curr.time + 1 - prev.time;
                res[prev.id] += interval;
                if (!s.empty()) { // 这里很重要，父函数的实际运行时间不包括子函数的运行时间
                    res[s.top().id] -= interval; // s.top()是父函数，因为每次统计函数运行时间都是直接累加，所以要把子函数的运行时间『先』减掉
                }
            }
        }
        return res;
    }
};