題目

給出一個非搶佔單執行緒CPU的 n 個函式執行日誌，找到函式的獨佔時間。

每個函式都有一個唯一的 Id，從 0 到 n-1，函式可能會遞迴呼叫或者被其他函式呼叫。

日誌是具有以下格式的字串：function_id：start_or_end：timestamp。

例如："0:start:0" 表示函式 0 從 0 時刻開始執行。"0:end:0" 表示函式 0 在 0 時刻結束。

函式的獨佔時間定義是在該方法中花費的時間，呼叫其他函式花費的時間不算該函式的獨佔時間。

你需要根據函式的 Id 有序地返回每個函式的獨佔時間。

示例 1:輸入: n = 2

logs =

["0:start:0",

"1:start:2",

"1:end:5",

"0:end:6"]

輸出:[3, 4]

說明：函式 0 在時刻 0 開始，在執行了 2個時間單位結束於時刻 1。

現在函式 0 呼叫函式 1，函式 1 在時刻 2 開始，執行 4 個時間單位後結束於時刻 5。

函式 0 再次在時刻 6 開始執行，並在時刻 6 結束執行，從而執行了 1 個時間單位。

所以函式 0 總共的執行了 2 +1 =3 個時間單位，函式 1 總共執行了 4 個時間單位。

說明：輸入的日誌會根據時間戳排序，而不是根據日誌Id排序。

你的輸出會根據函式Id排序，也就意味著你的輸出陣列中序號為 0 的元素相當於函式 0 的執行時間。

兩個函式不會在同時開始或結束。

函式允許被遞迴呼叫，直到執行結束。

1 <= n <= 100

解題思路分析

1、棧輔助；時間複雜度O(n)，空間複雜度O(n)

type Node struct {	Id        int	StartTime int	Wait      int}func exclusiveTime(n int, logs []string) []int {	res := make([]int, n)	stack := make([]Node, 0)	for i := 0; i < len(logs); i++ {		arr := strings.Split(logs[i], ":")		id, _ := strconv.Atoi(arr[0])		if arr[1] == "start" {			start, _ := strconv.Atoi(arr[2])			stack = append(stack, Node{				Id:        id,				StartTime: start,				Wait:      0,			})		} else {			end, _ := strconv.Atoi(arr[2])			node := stack[len(stack)-1]			stack = stack[:len(stack)-1]			total := end - node.StartTime + 1 - node.Wait			res[node.Id] = res[node.Id] + total			if len(stack) > 0 {				wait := end - node.StartTime + 1				stack[len(stack)-1].Wait = stack[len(stack)-1].Wait + wait			}		}	}	return res}

2、棧輔助；時間複雜度O(n)，空間複雜度O(n)

func exclusiveTime(n int, logs []string) []int {	res := make([]int, n)	stack := make([]int, 0)	var prev int	for i := 0; i < len(logs); i++ {		arr := strings.Split(logs[i], ":")		id, _ := strconv.Atoi(arr[0])		if arr[1] == "start" {			start, _ := strconv.Atoi(arr[2])			if len(stack) > 0 {				lastId := stack[len(stack)-1]				res[lastId] = res[lastId] + start - prev			}			stack = append(stack, id)			prev = start		} else {			end, _ := strconv.Atoi(arr[2])			lastId := stack[len(stack)-1]			stack = stack[:len(stack)-1]			res[lastId] = res[lastId] + end - prev + 1			prev = end + 1		}	}	return res}

總結

Medium題目，棧應用題目