LeetCode 636. 函数的独占时间

2020-06-30 HGNULB 约 5 分钟

文章信息 6 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

数组 栈

题目描述

✅ 636. 函数的独占时间

题意分析

根据单线程 CPU 的函数开始、结束日志，计算每个函数实际执行的总时长，排除它等待其他调用返回的时间。同一函数可能多次调用或递归调用，所有调用的独占时长按函数编号累加。

解法：栈模拟调用栈

核心思路

[!blue]
栈顶是当前执行者，按事件整段结算时间。 开始和结束日志之间不会发生调用切换，这一整段时间都归当时的栈顶。用栈保存尚未返回的调用链，prev 表示下一段尚未计入答案的时间起点，而不是简单记录上一条日志的时间戳。

遇到 start:t，新调用从时刻 $t$ 的开头接管 CPU。若此前栈非空，区间 [prev, t) 属于旧栈顶，给它累加 t - prev；随后压入新调用，并令 prev = t。若此前栈为空，这段是空闲时间，不计给任何函数。

遇到 end:t，当前调用在时刻 $t$ 的末尾结束，所以 [prev, t] 全部属于它，长度为 t - prev + 1。结算后弹栈，父调用最早从下一时刻继续执行，因此更新 prev = t + 1，避免父子重复领取结束时刻。

每次结算都从上一段结束后的第一个未计入时刻开始，且只分配给当前执行者，因此所有执行时间恰好计算一次。递归时同一编号仍需多次入栈，以保留不同调用层；这些调用最终写入同一个 answer[id]，自然完成按函数聚合。

解题步骤

1. 初始化结果、空调用栈和未结算起点。
2. 开始事件先结算旧栈顶，再压入新函数并更新起点。
3. 结束事件计入含末时刻的区间，再弹栈并移动到下一时刻。
4. 返回各函数累计时长。

代码实现

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] answer = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        int prev = 0;

        for (String log : logs) {
            String[] parts = log.split(":");
            int id = Integer.parseInt(parts[0]);
            String type = parts[1];
            int t = Integer.parseInt(parts[2]);

            if ("start".equals(type)) {
                if (!st.isEmpty()) {
                    // 新调用从本时刻开始，此前半开区间属于旧栈顶。
                    answer[st.peekLast()] += t - prev;
                }

                st.addLast(id);
                prev = t;
            } else {
                // 结束时刻仍计入当前调用，下一段从下一时刻开始。
                answer[st.peekLast()] += t - prev + 1;
                st.pollLast();
                prev = t + 1;
            }
        }

        return answer;
    }
}

func exclusiveTime(n int, logs []string) []int {
    answer := make([]int, n)
    st := make([]int, 0)
    prev := 0

    for _, log := range logs {
        id, isStart, t := parse636(log)

        if isStart {
            // 新调用从本时刻开始，此前半开区间属于旧栈顶。
            if len(st) > 0 {
                answer[st[len(st)-1]] += t - prev
            }
            st = append(st, id)
            prev = t
        } else {
            // 结束时刻仍计入当前调用，下一段从下一时刻开始。
            answer[st[len(st)-1]] += t - prev + 1
            st = st[:len(st)-1]
            prev = t + 1
        }
    }

    return answer
}

func parse636(log string) (int, bool, int) {
    i := 0
    for i < len(log) && log[i] != ':' {
        i++
    }
    id := atoi636(log[:i])
    j := i + 1
    for j < len(log) && log[j] != ':' {
        j++
    }
    typ := log[i+1 : j]
    t := atoi636(log[j+1:])
    return id, typ == "start", t
}

func atoi636(s string) int {
    x := 0
    for i := 0; i < len(s); i++ {
        x = x*10 + int(s[i]-'0')
    }
    return x
}

复杂度分析

• 时间复杂度：$O(n+L)$，n 为函数数，L 为日志总字符量，包含结果初始化和解析。
• 空间复杂度：结果 $O(n)$，调用栈 $O(D)$，其中 $D$ 为最大嵌套深度；Java 日志切分另需单条日志长度级的临时空间，Go 解析只额外保存下标和数值。

关键点总结

[!green]

• start 结算旧执行者的 [prev,t)，end 结算含 t 的区间，两种长度公式不同。
• 结束后的 prev 必须前进到 t+1。
• 同一函数编号可以在栈中出现多次，代表不同调用层。
• 题目给出合法的调用日志，结束事件对应当前栈顶；同一时刻开始并结束的调用也占用一个时间单位。

易错点总结

[!yellow]

• 结束不加一：单次同刻开始结束会被算成零。
• 嵌套返回后 prev 仍为 t：父调用会重复领取结束时刻。
• 开始时结算给新函数：把此前执行者的时间分错。
• 递归入栈先去重：破坏调用层数，后续返回无法对应。

相似题目

题目	难度	关联与区别
20. 有效的括号	简单	调用开始与结束具有栈式嵌套结构，先恢复当前活跃函数，再正确归属时间段。
394. 字符串解码	中等	同样使用栈保存外层状态并处理嵌套返回，本题累计执行时间，原题展开子串。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2020/88280888

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！