636. Exclusive Time of Functions

📘 題目敘述

在單執行緒 CPU 上，我們執行一個包含 n 個函式的程式。每個函式都有唯一的 ID，範圍是 0 到 n - 1。

函式呼叫會存在一個 call stack 中：

當函式開始執行時，它的 ID 會被 push 進 stack
當函式結束時，它的 ID 會從 stack 中 pop 出來

stack 最上面的函式，就是目前正在執行的函式。

每當一個函式開始或結束時，都會記下一筆 log，內容包含：

函式 ID
是開始還是結束
timestamp

你會拿到一個字串陣列 logs，其中 logs[i] 的格式是：

"{function_id}:{"start" | "end"}:{timestamp}"

例如：

"0:start:3" 表示函式 0 在 timestamp 3 的開始時刻開始執行
"1:end:2" 表示函式 1 在 timestamp 2 的結束時刻結束執行

注意：

一個函式可能會被呼叫多次
也可能遞迴呼叫自己

函式的 exclusive time，表示它真正執行的總時間，不包含它呼叫其他函式時被暫停的時間。

請回傳一個長度為 n 的陣列，其中第 i 個位置表示函式 i 的 exclusive time。

條件限制

1 <= n <= 100
2 <= logs.length <= 500
0 <= function_id < n
0 <= timestamp <= 10^9
不會有兩個 start event 發生在同一個 timestamp
不會有兩個 end event 發生在同一個 timestamp
每個函式的每個 start log 都一定會有對應的 end log

🧠 解題思路

這題的關鍵是要搞清楚：

現在 stack 最上面的函式，才是真正正在跑的那個函式。

所以我這份做法是：

先把每一筆 log 解析成比較好處理的結構
用一個 stack now 記目前正在呼叫鏈上的函式
用一個 pos 記「目前這段執行時間，是從哪個 timestamp 開始算的」

接著一筆一筆看 logs。

如果某筆 log 是 "start"：

代表有一個新函式要開始跑了
那在它開始之前，原本 stack 頂端那個函式已經先跑了一段時間
所以要先把這段時間加到那個函式身上
然後再把新函式 push 進 stack，並把 pos 更新成這個新函式開始的時間

如果某筆 log 是 "end"：

代表 stack 頂端這個函式執行到這裡結束
題目說 end 是在該 timestamp 的結束時刻
所以這一段時間長度要算：

l.time + 1 - pos

加完之後把它 pop 掉

然後把 pos 更新成 l.time + 1

因為下一個真正恢復執行的函式，是從下一個時間點開始算

所以這題最重要的不是單純用 stack，而是：

stack 負責知道現在誰在跑
pos 負責知道目前這段時間從哪裡開始算

也就是說，這題的核心就是：

用 stack 維護目前正在執行的函式，用 pos 記錄當前這段 CPU 時間的起點，遇到 start / end 時把這段時間正確加到 stack 頂端函式身上。

所有變數

Log：自訂結構，存一筆 log 解析後的內容
- id：函式 ID
- s：這筆 log 是 "start" 還是 "end"
- time：timestamp
tolog：把 log 字串轉成 Log 結構的函式
u：傳進 tolog 的原始 log 字串
p1：第一個 ':' 的位置
p2：第二個 ':' 的位置
cur：解析後的 Log
n：函式總數
logs：輸入的 log 字串陣列
now：stack，存目前呼叫鏈上的函式 ID
len：答案陣列，len[i] 表示函式 i 的 exclusive time
pos：目前這段正在累積的執行時間起點

🪜 主要流程步驟

1. 先把 log 字串拆成結構化資料

這個函式的用途是把像：

"0:start:3"

這種字串拆成：

id = 0
s = "start"
time = 3

這樣後面主流程在判斷時會比較清楚，不用每次都重新切字串。

2. 先準備 stack、答案陣列和時間起點 pos

stack<int> now;
vector<int> len(n, 0);
int pos = 0;

這裡三個東西的角色分別是：

now
- 記目前呼叫堆疊上的函式
- stack 頂端就是現在真正正在執行的函式
len
- 最後答案
- len[i] 表示函式 i 的 exclusive time
pos
- 記目前這段 CPU 執行時間，是從哪個 timestamp 開始計

3. 依序處理每一筆 log

for (string t : logs) {
    Log l = tolog(t);

這裡先把每一筆原始字串 t 解析成 Log l，接著再看它是 start 還是 end。

4. 如果遇到 start，先把前一個正在跑的函式補上時間

if (l.s == "start") {
    if (!now.empty()) {
        len[now.top()] += l.time - pos;
    }
    now.push(l.id);
    pos = l.time;
}

這段的意思是：

如果有新的函式在 l.time 開始，那表示在這之前：

原本 stack 頂端那個函式
已經從 pos 跑到 l.time - 1

所以它應該先累加這一段長度：

l.time - pos

注意這裡不是 +1，因為新函式是在 l.time 的開始時刻進來的，所以舊函式只跑到前一刻。

接著：

把新函式 l.id push 進 stack
把 pos 更新成 l.time

表示從現在開始，CPU 的時間要算到新函式頭上。

5. 如果遇到 end，表示 stack 頂端函式要結束了

else {
    len[now.top()] += l.time + 1 - pos;
    now.pop();
    pos = l.time + 1;
}

這段是整題最關鍵的地方。

題目特別說：

"end" 是在該 timestamp 的結束時刻結束

所以如果某個函式從 pos 開始跑，到 l.time 結束，那它這段真正跑的長度是：

l.time - pos + 1
也就是程式裡的 l.time + 1 - pos

這段時間要加到目前 stack 頂端那個函式身上。

加完後：

now.pop()
- 因為這個函式已經結束了
pos = l.time + 1
- 因為接下來如果有上一層函式恢復執行，會是從下一個時間點開始

6. 為什麼 pos 更新成 `l.time + 1`

這一點很重要。

假設某個函式在時間 5 的結束時刻結束，那它其實已經完整佔用了 timestamp 5。

所以之後下一個恢復執行的函式，不是從 5 開始，而是從：

也就是：

pos = l.time + 1;

這樣下一段時間計算才不會重複。

7. 為什麼這樣就能正確算 exclusive time

因為在單執行緒 CPU 上，同一時間只會有一個函式真正執行。

所以每次處理 log 時：

stack 頂端就是目前在跑的函式
pos 到這次事件時間之間的那一段 CPU 使用時間，一定全部屬於它

當遇到：

start
- 表示舊函式先暫停，新函式接手
end
- 表示目前函式跑完，上一層可能恢復

所以只要每次事件發生時，把事件前那一段時間正確補到 stack 頂端函式，就能把每個函式真正獨占 CPU 的時間全部累加出來。

8. 最後回傳 len

return len;

當所有 logs 都處理完之後，len[i] 就是函式 i 的 exclusive time，直接回傳即可。

⏱️ 複雜度

設 m = logs.length。

時間複雜度：O(m)
每一筆 log 都只會被解析與處理一次。
空間複雜度：O(n + m)
len 需要 O(n)，stack 在最壞情況下可能累積到 O(m) 層呼叫深度。

💻 程式碼實作

class Solution {
public:
    struct Log {
        int id;   // function id
        string s; // start or end
        int time; // time
    };
    Log tolog(const string u) {
        int p1 = u.find(':');
        int p2 = u.find(':', p1 + 1);

        Log cur;
        cur.id = stoi(u.substr(0, p1));
        cur.s = u.substr(p1 + 1, p2 - p1 - 1);
        cur.time = stoi(u.substr(p2 + 1));
        return cur;
    }
    vector exclusiveTime(int n, vector& logs) {
        stack now;
        vector len(n, 0);
        int pos = 0;
        for (string t : logs) {
            Log l = tolog(t);
            if (l.s == "start") {
                if (!now.empty()) {
                    len[now.top()] += l.time - pos;
                }
                now.push(l.id);
                pos = l.time;
            } else {
                len[now.top()] += l.time + 1 - pos;
                now.pop();
                pos = l.time + 1;
            }
        }
        return len;
    }
};

🔗 題目連結

https://leetcode.com/problems/exclusive-time-of-functions/