636. 函數的獨占時間

思路

建立一個stack，用來記錄當前進行的函數id。
當新的log紀錄讀取到新的工作開始時，將被打斷的函數結算運行時間。
如果是工作時間結束，將時間戳減去上一個函數開始運行的時間。

就算遇到的是嵌套的函數運行，比如 $[1,1,1,2,2,2,1,1,1]$，
前段的 $[1,1,1]$ 會在遇到 $2$ 時，將 $1$ 的運行時間結算。
後段的 $[1,1,1]$ 會在遇到最後一個 $1$ 時結算。

程式碼

單調棧

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> res(n);
        stack<int> stk;
        int prev_time = 0;
        string s;
        for(int i = 0; i < logs.size(); ++i) {
            stringstream ss(logs[i]);
            getline(ss, s, ':');
            int f_id = stoi(s);
            getline(ss, s, ':');
            bool isStart = s == "start";
            getline(ss, s, ':');
            int timestamp = stoi(s);
            if(isStart) {
                if(!stk.empty()) {
                    // 計算上一個正在執行的 function 跑了多久
                    res[stk.top()] += timestamp - prev_time;
                }
                stk.push(f_id);
                prev_time = timestamp;
            } 
            else{
                res[stk.top()] += timestamp - prev_time + 1;
                stk.pop();
                // 下一個計算起點是 end 之後的下一秒
                prev_time = timestamp + 1;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(L)$，其中 $L$ 為logs的長度。
• 空間複雜度：$O(n)$