636. 函式的獨佔時間 : 簡單棧運用模擬題

題目描述

這是 LeetCode 上的 636. 函式的獨佔時間 ，難度為 中等 。

Tag : 「模擬」、「棧」

有一個單執行緒 CPU 正在執行一個含有 n 道函式的程式。每道函式都有一個位於  0 和 n-1 之間的唯一識別符號。

函式呼叫 儲存在一個呼叫棧上 ：當一個函式呼叫開始時，它的識別符號將會推入棧中。而當一個函式呼叫結束時，它的識別符號將會從棧中彈出。識別符號位於棧頂的函式是當前正在執行的函式。每當一個函式開始或者結束時，將會記錄一條日誌，包括函式識別符號、是開始還是結束、以及相應的時間戳。

給你一個由日誌組成的列表 logs ，其中 logs[i] 表示第 i 條日誌訊息，該訊息是一個按 "{function_id}:{"start" | "end"}:{timestamp}" 進行格式化的字串。例如， "0:start:3" 意味著識別符號為 0 的函式呼叫在時間戳 3 的 起始開始執行 ；而 "1:end:2" 意味著識別符號為 1 的函式呼叫在時間戳 2 的末尾結束執行。注意，函式可以呼叫多次，可能存在遞迴呼叫 。

函式的「獨佔時間」定義是在這個函式在程式所有函式呼叫中執行時間的總和，呼叫其他函式花費的時間不算該函式的獨佔時間。例如，如果一個函式被呼叫兩次，一次呼叫執行 2 單位時間，另一次呼叫執行 1 單位時間，那麼該函式的獨佔時間為 2 + 1 = 3 。

以陣列形式返回每個函式的獨佔時間，其中第 i 個下標對應的值表示識別符號 i 的函式的獨佔時間。

輸入：n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]

輸出：[3,4]

解釋：
函式 0 在時間戳 0 的起始開始執行，執行 2 個單位時間，於時間戳 1 的末尾結束執行。 
函式 1 在時間戳 2 的起始開始執行，執行 4 個單位時間，於時間戳 5 的末尾結束執行。 
函式 0 在時間戳 6 的開始恢復執行，執行 1 個單位時間。 
所以函式 0 總共執行 2 + 1 = 3 個單位時間，函式 1 總共執行 4 個單位時間。

示例 2：

輸入：n = 1, logs = ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]

輸出：[8]

解釋：
函式 0 在時間戳 0 的起始開始執行，執行 2 個單位時間，並遞迴呼叫它自身。
函式 0（遞迴呼叫）在時間戳 2 的起始開始執行，執行 4 個單位時間。
函式 0（初始呼叫）恢復執行，並立刻再次呼叫它自身。
函式 0（第二次遞迴呼叫）在時間戳 6 的起始開始執行，執行 1 個單位時間。
函式 0（初始呼叫）在時間戳 7 的起始恢復執行，執行 1 個單位時間。
所以函式 0 總共執行 2 + 4 + 1 + 1 = 8 個單位時間。

示例 3：

輸入：n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]

輸出：[7,1]

解釋：
函式 0 在時間戳 0 的起始開始執行，執行 2 個單位時間，並遞迴呼叫它自身。
函式 0（遞迴呼叫）在時間戳 2 的起始開始執行，執行 4 個單位時間。
函式 0（初始呼叫）恢復執行，並立刻呼叫函式 1 。
函式 1在時間戳 6 的起始開始執行，執行 1 個單位時間，於時間戳 6 的末尾結束執行。
函式 0（初始呼叫）在時間戳 7 的起始恢復執行，執行 1 個單位時間，於時間戳 7 的末尾結束執行。
所以函式 0 總共執行 2 + 4 + 1 = 7 個單位時間，函式 1 總共執行 1 個單位時間。

示例 4：

輸入：n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:7","1:end:7","0:end:8"]

輸出：[8,1]

示例 5：

輸入：n = 1, logs = ["0:start:0","0:end:0"]

輸出：[1]

提示：

• $1 <= n <= 100$
• $1 <= logs.length <= 500$
• $0 <= function_id < n$
• $0 <= timestamp <= 10^9$
• 兩個開始事件不會在同一時間戳發生
• 兩個結束事件不會在同一時間戳發生
• 每道函式都有一個對應  "start" 日誌的 "end" 日誌

模擬

我們使用「棧」來模擬執行過程：當一個函式被呼叫（ op = start ）時，壓入棧內，當函式呼叫完成（ op = end ）時，從棧頂彈出（此時棧頂元素必然是該結束函式的入棧記錄），使用變數 cur 記錄當前時間。

從前往後處理所有的 $log[i]$，根據 $log[i]$ 是屬於函式呼叫還是函式結束進行分情況討論：

• 當 $log[i]$ 為函式呼叫：此時從該函式的呼叫發起時間 ts 到上一次記錄的當前時間，都是前一函式的執行時間，因此可以將 ts - cur 累加到棧幀中的前一函式。即若棧不為空，則將該時間累加到棧頂對應的函式上，然後將 $log[i]$ 入棧，同時更新當前時間；
• 當 $log[i]$ 為函式結束：此時棧頂元素必然是該函式的呼叫記錄，此時 $log[i]$ 的結束時間與上一次記錄的當前時間的時長 ts - cur + 1 ，必然是該函式的執行時間，將其累加到當前函式中，並更新當前時間。

Java 程式碼：

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ans = new int[n];
        Deque<Integer> d = new ArrayDeque<>();
        int cur = -1;
        for (String log : logs) {
            String[] ss = log.split(":");
            int idx = Integer.parseInt(ss[0]), ts = Integer.parseInt(ss[2]);
            if (ss[1].equals("start")) {
                if (!d.isEmpty()) ans[d.peekLast()] += ts - cur;
                d.addLast(idx);
                cur = ts;
            } else {
                int func = d.pollLast();
                ans[func] += ts - cur + 1;
                cur = ts + 1;
            }
        }
        return ans;
    }
}

TypeScript 程式碼：

function exclusiveTime(n: number, logs: string[]): number[] {
    const ans = new Array<number>(n).fill(0)
    const stk = new Array<number>()
    let he = 0, ta = 0, cur = -1
    for (let log of logs) {
        const ss = log.split(":")
        const idx = Number(ss[0]), ts = Number(ss[2])
        if (ss[1] == "start") {
            if (he < ta) ans[stk[ta - 1]] += ts - cur
            stk[ta++] = idx
            cur = ts
        } else {
            const func = stk[--ta]
            ans[func] += ts - cur + 1
            cur = ts + 1
        }
    }
    return ans
};

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$

最後

這是我們「刷穿 LeetCode」系列文章的第 No.636 篇，系列開始於 2021/01/01，截止於起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的程式碼。如果涉及通解還會相應的程式碼模板。

為了方便各位同學能夠電腦上進行除錯和提交程式碼，我建立了相關的倉庫： http://github.com/SharingSou... 。

在倉庫地址裡，你可以看到系列文章的題解連結、系列文章的相應程式碼、LeetCode 原題連結和其他優選題解。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:

本文由mdnice多平臺釋出