LeetCode 636. 函数的独占时间

2020-06-30 HGNULB 约 9 分钟

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

分类

题目描述

✅ 636. 函数的独占时间

题意分析

要什么：单核 CPU 上按时间顺序给出一串日志，形如 id:start:t 或 id:end:t，函数之间可以互相嵌套调用（也可以递归调用自己）。要求每个函数独占的执行时长，即它自己在跑、且没有被别的调用压在上面的那部分时间总和。
约束透露的信号：单核意味着任意时刻只有一个函数在真正执行，而嵌套调用天然构成后进先出的层级关系——这两点合起来就是一个只能靠栈来还原的运行时结构。日志按时间戳升序给出，说明可以一遍线性扫描，无需排序。
边界：start 的时间戳表示该时刻刚开始占用，而 end 的时间戳表示该时刻执行完毕后才结束，也就是这一整个时间单元也算它的，所以以 end 收尾的区间长度是 t - prev + 1 而不是 t - prev。递归调用会让同一个 id 在栈里出现多次，累加时必须按栈顶而不是按日志里的 id 归属。日志一定合法配对，栈不会提前空掉。

解法：栈模拟调用栈

核心思路

朴素想法是开一个长度等于总时间跨度的数组，逐个时间单元记录「此刻栈顶是谁」，最后统计每个 id 出现了多少个时间单元。这是对的，也最容易理解，但时间戳可以到 $10^9$ 量级，按时间单元展开会直接爆掉。
瓶颈在于：相邻两条日志之间，栈顶是不变的，我们逐格记录纯属重复劳动。只要知道「这段区间有多长、当前栈顶是谁」，一次加法就能顶掉整段。
于是把时间轴按日志的时间戳切成若干段，每段整体归属于一个函数。要维护的不变量是：栈里从底到顶保存的是当前尚未返回的调用链（每个元素是函数 id，同一函数递归时会重复出现），栈顶就是此刻真正占用 CPU 的那次调用；变量 prev 表示「当前这一段尚未结算的时间片的起点」，即 [prev, 当前事件时刻) 这段时间尚未记账。
每读到一条日志，就先把 prev 到该事件之间的时间片结算给栈顶，再根据事件类型调整栈与 prev。这样任何一格时间只会被结算一次、且只算给唯一的栈顶，独占语义自动成立。

解题步骤

初始化 answer 数组全 0、空栈、prev = 0。为什么 prev 从 0 起：第一条日志一定是某个函数的 start，此时栈为空，没有任何时间需要结算，prev 的初值只要不引发误算即可，0 最自然。

逐条日志解析出 id、是否为 start、时间戳 t。为什么必须先解析成三元组：后面的分支逻辑对两类事件的处理完全不同，混在字符串里判断既慢又容易写错。

遇到 start 且栈非空时，先执行 answer[栈顶] += t - prev。为什么是 t - prev 而不带 +1：新函数从第 t 个时间单元开始占用 CPU，所以老函数实际拥有的是 [prev, t - 1]，长度恰好 t - prev；第 t 格已经属于新函数，不能重复计给老函数。

然后把 id 压栈并令 prev = t。为什么压 id 而不是记「当前函数」这一个变量：调用可以嵌套任意深，被打断的老函数在子调用返回后还要继续计时，只有栈能记住整条链；递归时同一 id 多次入栈也不会互相干扰，因为我们只关心「栈顶是谁」。

遇到 end 时执行 answer[栈顶] += t - prev + 1，然后弹栈并令 prev = t + 1。为什么这里要 +1：end 的时间戳是闭区间右端，第 t 格仍归它执行，区间是 [prev, t]，长度 t - prev + 1。为什么 prev 要跳到 t + 1：第 t 格已经结算完毕，下一段未记账的时间从 t + 1 开始，若仍写 prev = t 会让这一格被下一个函数重复领走。

以 n = 2、logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"] 走一遍。初始 answer = [0, 0]、栈空、prev = 0。第一条 0:start:0：栈空跳过结算，压入 0，栈为 [0]，prev = 0。第二条 1:start:2：栈顶是 0，结算 answer[0] += 2 - 0 = 2（函数 0 独占了第 0、1 两格），压入 1，栈为 [0, 1]，prev = 2。第三条 1:end:5：栈顶是 1，结算 answer[1] += 5 - 2 + 1 = 4（第 2 到 5 共四格），弹出 1，栈回到 [0]，prev = 6。第四条 0:end:6：栈顶是 0，结算 answer[0] += 6 - 6 + 1 = 1（只剩第 6 格），弹出 0，栈空，prev = 7。返回 [3, 4]：函数 0 拥有第 0、1、6 格共 3 格，函数 1 拥有第 2 到 5 格共 4 格，合计 7 格恰好等于 [0, 6] 的总长度，没有重叠也没有遗漏。

代码实现

// 核心实现：栈模拟调用栈，维护必要状态并避免重复处理。
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(m)$，$m$ 为日志条数。凭什么：每条日志只被解析一次，每条最多引起一次入栈和一次出栈，栈操作是均摊 $O(1)$；解析单条日志的开销与字符串长度成正比而该长度有常数上界。

空间复杂度：$O(n + m)$。凭什么：答案数组占 $O(n)$；调用栈在全是嵌套 start 的极端日志下会堆到 $O(m)$ 深；除此之外只有几个标量。

关键点总结

看到「嵌套 / 配对 / 后进先出」就该条件反射想到栈。本题的栈不是用来做括号匹配，而是用来还原运行时的调用链，栈顶天然回答了「此刻谁在跑」这个问题。

时间戳范围很大而事件很少时，不要按时间单元展开，要按事件把时间轴切片。「用 prev 记住上一次结算点，遇到事件就整段结算」是扫描线类问题的通用手法，区间合并、日程安排里都能复用。

区间端点的开闭语义必须在动手前定死。本题的 start 是左闭、end 是右闭，因此一个 +1 和一个 prev = t + 1 成对出现；把它们理解成「同一个约定的两个侧面」就不会顾此失彼。

递归调用是这题的隐藏考点：同一个 id 会在栈中多次出现，因此累加必须以栈顶元素为准，绝不能用日志里刚读到的 id——在 end 事件里两者恰好相同，但在 start 事件里两者截然不同。

面试视角：写完后主动用一组含递归的日志（如 ["0:start:0","0:start:2","0:end:5","0:end:6"]）自测，并解释「为什么 answer[0] 应当是 7」，比等面试官出反例更有说服力。

易错点总结

错误写法：end 事件写成 answer[栈顶] += t - prev，漏掉 +1；用例 ["0:start:0","0:end:0"] → 得到 0，正确答案是 1，函数只跑一格时会被整段吞掉。

错误写法：end 之后写 prev = t 而不是 t + 1；用例 ["0:start:0","0:end:2","1:start:3","1:end:4"] → 第 2 格被函数 0 结算后又被算进函数 1 的起点区间，answer[1] 变成 3 而不是 2。

错误写法：start 事件也加 1，写成 t - prev + 1；用例 ["0:start:0","1:start:2","1:end:2","0:end:3"] → 第 2 格既算给 0 又算给 1，answer 求和超过总时间跨度，返回 [3,1] 而不是 [2,1]。

错误写法：start 时不判断栈是否为空就结算；用例 ["0:start:5"] 开头 → 栈为空时访问栈顶直接抛空指针 / 下标越界异常。

错误写法：end 事件把时间累加到日志里读出的 id 上而不是栈顶（虽然二者相同），但在 start 事件里也误用了刚读到的 id；用例 ["0:start:0","1:start:2","1:end:5","0:end:6"] → 第二条日志会把 2 - 0 = 2 记到函数 1 头上，返回 [1,6] 而不是 [3,4]。

错误写法：用一个「当前函数」变量代替栈；用例 ["0:start:0","1:start:2","1:end:5","0:end:6"] → 函数 1 返回后无法恢复出「现在该轮到 0」，末尾的结算落到错误的函数上。

错误写法：没考虑同一函数递归，压栈时先查重、已在栈中就不重复压；用例 ["0:start:0","0:start:2","0:end:5","0:end:6"] → 第二次 end 时栈已空，弹栈抛异常；正确做法是照常重复压入，最终 answer[0] = 7。

错误写法：用 Integer.parseInt(log.charAt(0) + "") 之类只取一位来解析 id；用例 ["12:start:0","12:end:3"] → id 被截成 1，写入错误下标甚至越界。

错误写法：按时间单元逐格模拟，开一个长度为最大时间戳的数组；用例 ["0:start:0","0:end:1000000000"] → 内存直接爆掉，而正确解法只需常数次加法。

错误写法：遍历结束后再统一把「剩余栈内元素」结算一遍；用例任意合法日志 → 日志保证配对完整，遍历结束时栈必为空，多余的收尾逻辑要么无效要么在实现里访问空栈报错。

相似题目

题目	难度	考察点
20. 有效的括号	简单	只判断配对是否合法，栈里不需要携带任何数值信息
856. 括号的分数	中等	栈里存的是子结构的累计得分，弹栈时要把子层结果并回父层
1190. 反转每对括号间的子串	中等	同为嵌套结构，但栈保存的是待还原的字符串片段而非时间点