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​

​ 的函數的獨占時間。

示例 1：

輸入：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]      

提示：

• 兩個開始事件不會在同一時間戳發生
• 兩個結束事件不會在同一時間戳發生
• 每道函數都有一個對應​

  ​"start"​

  ​​ 日志的​

  ​"end"​

  ​ 日志

模拟

我們使用「棧」來模拟執行過程：當一個函數被調用（​

​op = start​

​​）時，壓入棧内，當函數調用完成（​

​op = end​

​​）時，從棧頂彈出（此時棧頂元素必然是該結束函數的入棧記錄），使用變量 ​

​cur​

​ 記錄目前時間。

從前往後處理所有的 ，根據

• 當為函數調用：此時從該函數的調用發起時間​​

  ​ts​

  ​​ 到上一次記錄的目前時間，都是前一函數的執行時間，是以可以将​

  ​ts - cur​

  ​​ 累加到棧幀中的前一函數。即若棧不為空，則将該時間累加到棧頂對應的函數上，然後将
• 當為函數結束：此時棧頂元素必然是該函數的調用記錄，此時的結束時間與上一次記錄的目前時間的時長​​

  ​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      

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      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.636​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

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