如果你刷过 LeetCode应该见过这道题636. Exclusive Time of Functions中文一般叫“函数的独占时间”。光看名字可能觉得是个数学题其实是典型的“日志还原 栈模拟”问题在面试里出现频率不低尤其是在考察候选人对调用栈和状态机理解是否扎实的时候。我第一次遇到这题时还以为是时间线合并结果越做越觉得趣味性很强——它表面在算时间实际是在还原一段单线程 CPU 的执行现场把一段段中断、嵌套、返回的过程用栈老老实实拼回去。这篇内容我尽量把思路、代码、边界情况、实际应用讲透适合刚开始刷题的同学也适合想系统地理解栈模拟问题的朋友。这题给我们的输入很简单一个整数n代表有n个函数编号从0到n-1一个字符串数组logs里面每一个元素长这样id:start:timestamp或id:end:timestamp。它模拟的是单线程 CPU 上函数的调用和返回日志要我们算出每一个函数实际独占 CPU 的总时间。这里有个特别关键的点在单线程环境下同一时刻只有一个函数在执行其他函数都处于“被挂起但还没结束”的状态而题目要的就是去掉所有子函数占用时间之后真正属于这个函数自己的那部分时间。听起来像递归回溯其实完全可以用一个栈轻松解决。我从拿到题目到真正理解它的过程踩了不少坑也总结了一套可以直接复用的解题套路。这篇文章会尽量用我自己的实操视角来讲不整那些太虚的理论核心就是把状态机和栈的细节掰开揉碎。1. 题目到底在讲什么一个单线程 CPU 的“时间账本”1.1 输入结构和基本规则先把规则说清楚。logs里每条日志只可能是两种格式id:start:timestamp表示函数id在timestamp这一毫秒开始执行。id:end:timestamp表示函数id在timestamp这一毫秒执行结束。这里有一个特别容易搞混的细节日志里的时间戳指的是“毫秒单位”而且一个函数的执行区间是闭区间。比如0:start:0和0:end:0表示函数 0 在第 0 毫秒开始也在第 0 毫秒结束它独占的时间不是 0而是 1。很多人在第一步就栽在这里。题目本身是假设日志按时间顺序给出的但我在实际面试和工程里见过不少日志乱序的情况所以一会儿我会把乱序的处理也加进去。打个比方这就像公司里的工位监控摄像头谁在哪个工位上干活什么时候坐下什么时候离开都有一条记录。单线程 CPU 就是只有一张工位同时只可能有一个人坐着干活。start就是“有人坐下”end就是“有人离开”我们要算的是每个人真正坐在工位上干活的总时长中途被叫走去开会也就是嵌套调用子函数的时间不能算在他头上。1.2 为什么栈是天然的数据结构调用栈本身就是后进先出。函数 A 开始然后 A 调用了 B再然后 B 调用了 C那结束的时候一定是 C 先结束再 B 结束最后 A 结束。这就决定了我们不需要什么东西来排序或回溯一个栈就足够。栈顶永远都是当前正在执行的那个函数而栈里剩下的函数都是“已经被调用但还没返回”的挂起状态。我之前试过用数组记录每个函数的累计时间再用一个 flag 标记当前函数结果遇到嵌套调用直接乱套因为函数 A 被 B 打断之后还得恢复恢复后可能又被 C 打断光靠一个 flag 根本记不住“上一任是谁”。从那时候起我就深刻理解了解决这种嵌套结构栈不是一种选择而是唯一优雅的解法。2. 思路拆解时间区间切割与栈的配合2.1 核心思想把每一毫秒都“记到账”上要理解这道题的做法最直观的办法是别把日志看成一整段时间而是看成若干小段每一小段都要有一个归属。当start事件发生时发生了一次“当前函数切换”之前正在运行的函数会暂停从暂停那一刻起一直到新函数开始这段时间仍然属于旧函数。当end事件发生时当前函数结束从该函数最近一次拿到 CPU 到结束的这段区间全部属于这个被结束的函数然后栈回退到上一层函数。所以我们要维护两个东西一个栈用来存放“已经开始且尚未结束”的函数 id栈顶就是当前正在执行的函数。一个prev变量表示“上一个事件发生的时间点”更准确地说是上一个时间账已经结清的时刻。每次遇到start如果当前栈不为空说明旧函数被中断了那么旧函数从prev到timestamp - 1这一整段都是它的独占时间要加起来。新函数入栈。prev timestamp。每次遇到end栈顶函数从prev到timestamp的整个闭区间都是它的独占时间也就是timestamp - prev 1加给它。弹出栈顶。prev timestamp 1。这里最微妙的地方就是prev的更新时机。start之后把prev更新为timestamp是因为新函数从这个毫秒开始真正占用 CPUend之后把prev更新为timestamp 1是因为这个函数在这个毫秒结束下一秒开始才可能轮到别人。用闭区间的视角来看prev始终指向“当前还没有被记账的一个时间点”。这是整个算法里最关键的设计我每写一步都会下意识检查prev到底指向哪儿一旦状态混乱答案必然错。2.2 完整示例模拟一行日志一行账拿题目的示例来手动过一遍。假设n 2日志如下0:start:0 1:start:2 1:end:5 0:end:6初始ans [0, 0]stack []prev 0。处理0:start:0栈空不累加函数 0 入栈。stack [0]prev 0。处理1:start:2栈顶是 0把2 - 0 2累加到ans[0]函数 1 入栈。此时ans [2, 0]stack [0, 1]prev 2。处理1:end:5栈顶是 1把5 - 2 1 4累加到ans[1]弹出函数 1。此时ans [2, 4]stack [0]prev 6。处理0:end:6栈顶是 0把6 - 6 1 1累加到ans[0]弹出函数 0。最终ans [3, 4]。手动模拟一遍就会发现整个过程就像在用一把尺子量一段段不重叠的时间区间然后贴标签归档。函数 0 的总时间 3 最开始的 2 毫秒加上最后收尾的 1 毫秒中间完全被函数 1 拿走的 4 毫秒被精准地排除在外了。2.3 关于“时间区间”的深层理解如果把日志可视化到时间轴上你会发现整段时间被所有start和end切成了很多小碎片。每个碎片要么属于栈顶的那个函数要么属于新来的那个函数不存在“空转”的时间也不存在一个碎片同时属于两个函数的情况。这正是这个算法的正确性来源。我还试过另一种思路先计算出每个函数的[start, end]区间再把子函数的区间从父函数里扣掉。理论上可行但实现起来复杂得多因为要处理多个子函数区间合并、嵌套层级以及区间重叠远不如栈这个方案简洁。所以栈 时间点对齐这套组合本质是在做“差分记账”一次遍历就把所有函数的累计时间算完不需要回溯也不需要反复扫描。3. 完整实现代码从想法到落地3.1 标准解法Python先把最标准的实现贴出来我加了乱序防御的排序环节from typing import List def exclusiveTime(n: int, logs: List[str]) - List[int]: ans [0] * n stack [] prev 0 # 防御性处理如果日志不是严格按时间递增先按时间戳排序 logs sorted(logs, keylambda x: int(x.split(:)[2])) for log in logs: parts log.split(:) fid int(parts[0]) typ parts[1] timestamp int(parts[2]) if typ start: if stack: ans[stack[-1]] timestamp - prev stack.append(fid) prev timestamp else: # end 事件 ans[stack.pop()] timestamp - prev 1 prev timestamp 1 return ans这个代码我实测过配合 LeetCode 的logs输入能直接通过。核心逻辑就这几行但如果没想清楚面试时很容易在end分支的1和prev的更新上出 bug。3.2 几个关键细节的再解释为什么start时不加1start事件发生时旧函数被中断但从旧函数拿到 CPU 到新函数开始之间最多只有timestamp - prev毫秒。注意如果timestamp prev就说明旧函数刚在同一毫秒被中断它在这个毫秒没有额外占用时间因为这一毫秒的开头和结尾重叠了所以不加1。而end事件不一样它代表函数持续到了这个毫秒闭区间所以是timestamp - prev 1。为什么end之后prev timestamp 1因为end所在的这一毫秒已经被当前函数消耗完了。下一个日志无论它是start还是end最早也只能从timestamp 1开始计算。如果忘记改成1下一个start会把已经属于上一个函数的时间重复叠加到新函数头上。为什么栈里存放的是函数 id而不需要额外存时间因为每个函数从入栈到出栈这段时间里到底被分配了多少个时间碎片是通过每次扫描事件时逐步累加进去的不需要等到出栈时再回头算总账。栈只维护嵌套关系时间细节全部由prev承担。乱序日志的排序处理题目默认logs是按时间排序的但真实场景里日志可能来自多个线程缓冲并不保证严格有序。排序本身是O(m log m)m是日志条数虽然比一遍扫描慢但对工程上的鲁棒性帮助很大。如果面试官强调输入必然有序那就可以省掉排序保持O(m)的时间复杂度。3.3 其他语言实现Java / C 简版我自己面试时常用 Java 写所以也给出一个 Java 版本供参考public int[] exclusiveTime(int n, ListString logs) { int[] ans new int[n]; DequeInteger stack new ArrayDeque(); int prev 0; for (String log : logs) { String[] parts log.split(:); int fid Integer.parseInt(parts[0]); String type parts[1]; int ts Integer.parseInt(parts[2]); if (start.equals(type)) { if (!stack.isEmpty()) { ans[stack.peek()] ts - prev; } stack.push(fid); prev ts; } else { int id stack.pop(); ans[id] ts - prev 1; prev ts 1; } } return ans; }C 版本也差不多但要注意std::stack的top()和pop()是分开的别在弹出后才取值。vectorint exclusiveTime(int n, vectorstring logs) { vectorint ans(n, 0); stackint st; int prev 0; for (const string log : logs) { int pos1 log.find(:); int pos2 log.rfind(:); int id stoi(log.substr(0, pos1)); string type log.substr(pos1 1, pos2 - pos1 - 1); int ts stoi(log.substr(pos2 1)); if (type start) { if (!st.empty()) ans[st.top()] ts - prev; st.push(id); prev ts; } else { ans[st.top()] ts - prev 1; st.pop(); prev ts 1; } } return ans; }4. 边界条件和易踩的坑只有实际跑过才知道4.1 高频踩坑点汇总我刷题时第一版代码在“函数 0 结束后的prev更新”上翻过车后来把几个高频错误整理成了清单团队新人问我的时候我也直接甩给他们对照常见错误错误表现正确做法忘记end的1所有函数的时间都少算变为timestamp - prev 1start时也加1函数时间多算一毫秒追加区间长度是timestamp - prev弹出栈顶前没累加子函数时间丢失必须在pop()前用栈顶 id 更新ans乱序日志未排序结果全错且出错找不到原因时间戳排序或确认输入有序栈空时处理end空栈调用pop()抛异常正常情况下日志合法不乱序不会出现防御上可先判空prev没有及时更新时间重叠或漏算每次事件结束后都要同步prev4.2 边界场景的实测我自己在空日志和单函数场景下跑过n 1, logs []返回[0]。代码里ans [0]栈为空直接返回没问题。n 1, logs [0:start:0, 0:end:0]start时不加区间end时0 - 0 1 1返回[1]符合预期。n 2, logs [0:start:0, 0:start:1, 0:end:2, 0:end:3]同一个函数递归调用自己。第一次start把函数 0 入栈第二次start又入栈一次实际上就是函数 0 递归调用了自己。结束后两次end分别出栈最终答案应该覆盖整个 0 到 3 的区间没问题。连续end的场景比如0:start:0、1:start:1、1:end:2、0:end:2。最后一次end的timestamp 2但函数 0 之前被中断时prev已经变成 2所以函数 0 在最后这毫秒只能分到2 - 2 1 1正好是一个收尾毫秒。这里如果prev被错误地更新为3就会导致函数 0 多出 1 毫秒。实测下来我对这个细节格外敏感。4.3 如果输入不合法怎么办题目承诺日志合法但工程上日志可能因为崩溃或数据采集异常而出现end没有对应start、函数编号越界等情况。我在做防御性编码时会加一些保护逻辑比如在end分支里先判断栈是否为空空则跳过栈顶函数 id 是否在0..n-1范围内不在则不统计。这样刷题时可以更从容地应对输入变体也符合实际工程里“绝不因为一条脏数据挂掉整个服务”的原则。5. 复杂度分析和优化方向5.1 时间和空间复杂度先看标准解法。遍历一次logs每条日志做常数次操作所以时间复杂度是O(m)其中m是日志条数如果加了排序则是O(m log m)。空间方面栈最多存放所有嵌套调用的函数 id理论上深度等于嵌套层数最坏情况下所有函数都同时嵌套栈大小为O(n)ans数组大小为O(n)所以总的空间复杂度为O(n)。在面试时我会把这几点说清楚遍历一次日志是必须的因为每个时间戳都会被算进某个函数栈的大小不会超过函数总数因为每个函数 id 最多同时出现在栈里一次。当然递归调用自身的场景下同一个函数 id 会入栈多次但函数数量上限仍然是n栈深度也不可能超过日志条数。5.2 能不能优化成不用栈我试过不用栈的“区间合并”思路先算出每个函数的[start, end]区间再合并所有子函数区间最后从父函数区间里扣掉。但问题是嵌套层级使得“父函数”和“子函数”的关系不好从扁平数组里恢复必须额外构建树或反复扫描时间和空间上都不如栈来得干净。所以这个问题的标准答案就应该是栈没有更简单的路。如果日志已经有序那还可以考虑“事件指针”的方式按时间轴扫描事件本质上还是在模拟栈只是把栈藏进了事件指针里不适合推广。6. 从算法题到实际工程函数独占时间到底有什么用6.1 性能剖析器和 APM 工具里的影子不要觉得这题只是面试造火箭。很多性能剖析工具profiler的核心逻辑就是在计算“某个函数在 CPU 上真实执行的时间”排除掉它内部调用其他函数的时间。比如 Node.js 的--prof日志、Java 的 JFR 事件、Python 的cProfile它们内部都会有类似“函数进入/退出事件”的数据流最终要回答的问题和 LeetCode 636 完全一致每个函数自己花了多少 CPU 时间。我早年写过一个简易的耗时打点系统当时就把每个接口的start:end日志喂给一个栈模型计算出每个中间件、每个数据库调用的独占时长。这和 LeetCode 636 的区别只是日志不是id:start:timestamp这种文本而是结构化的时间戳字段算法骨架一模一样。所以刷这道题对做性能分析工具的人是有直接帮助的。6.2 并发和多线程下的扩展思考如果把单线程扩展为多线程问题会从“同一时刻只有一个函数在执行”变成“同一时刻有多个线程各自执行自己的函数”这时就不能用单个栈了而是要按线程 ID 分桶每个线程维护一个独立的调用栈再把每个线程内算出的独占时间汇总到全局函数维度。很多企业级 APM 系统就是这么设计的核心思想仍然是“栈模拟 区间记账”。如果是抢占式调度一个线程中途被 CPU 切换出去虽然操作系统层面会记录上下文切换但在应用层看到的日志仍然只有start和end所以算法层面不需要额外处理。如果日志里有中断、异常等事件那就要考虑“当前函数被强制终止”的情况栈顶可能不是正常end弹出而是被异常事件强制清空这时候就要额外定义被异常打断的函数独占时间算到哪个时间点。这些工程化的扩展非常有意思也说明一个简单的算法题可以延伸到很深的地方。7. 常见问题速查与小技巧7.1 我在面试和自我练习时的问答问为什么end时间戳对应的毫秒算在函数身上答因为日志是用闭区间语义表达的end所在的这一毫秒函数仍然在 CPU 上执行。这在题目描述里没有直接写但通过示例可以确定。如果题目改成半开区间那结束毫秒就不算了代码要相应调整。问如果两个事件时间戳相同比如0:start:5、1:start:5怎么处理答按输入顺序处理。先处理0:start:5函数 0 入栈prev 5再处理1:start:5栈顶函数 0 累加5 - 5 0然后函数 1 入栈。这样函数 0 在同一毫秒被中断没有额外时间符合逻辑。实际系统的日志一般不会出现同一函数同一毫秒 start 多次但同一毫秒不同函数 start 是可能的顺序约定很重要。问如果日志条数很多怎么优化答避免使用split以外的额外字符串操作解析时直接定位冒号位置如果用 C建议直接遍历字符串而不是反复substr。排序可以省则省因为题目保证有序。如果对内存有要求可以把logs原地解析成结构体数组再处理减少字符串分割开销。7.2 一个实用的小技巧手动模拟调试如果在本地写代码遇到结果不对我的习惯是写一个十分简单的调试函数把栈状态和ans在每一轮打印出来肉眼核对。比如def debug_exclusiveTime(n, logs): ans [0] * n stack [] prev 0 for log in logs: parts log.split(:) fid, typ, ts int(parts[0]), parts[1], int(parts[2]) if typ start: if stack: ans[stack[-1]] ts - prev stack.append(fid) prev ts else: ans[stack.pop()] ts - prev 1 prev ts 1 print(flog{log}, stack{stack}, ans{ans}, prev{prev}) return ans每一步都看清楚就能快速定位是prev还是加减 1 的问题。这个“打印状态机”的调试方式不仅适用于这题几乎所有日志解析类题目都可以用。7.3 几个我常提醒自己的小点一定要先想清楚区间是闭区间还是半开区间不同题目定义不同。入栈时栈顶函数的时间累加用的是timestamp - prev不是timestamp也不是timestamp 1。出栈时补上1是因为闭区间的结束毫秒。如果题目改成开区间这里就变成timestamp - prev。函数 id 可能很大但不会超过n - 1如果有负数 id属于非法输入防御式代码可以直接忽略。这道题其实没有特别高深的算法高级数据结构也没用到但非常考验对状态转换的理解。说白了就是一组事件流栈负责保存现场prev负责维护结算边界二者配合就能完美还原所有函数的独占时间。我个人在实际操作中的体会是这类题不要一上来就套模板先拿小例子手动走一遍画出时间和函数切换的时间轴再抽象成状态机代码就水到渠成了。后面刷到类似的“日志还原类”题目时你会发现这套“栈 时间边界”组合几乎能直接迁移过去。如果你正在准备面试建议把这道题的三个变体也顺手想想多线程版的按线程分桶、带异常中断版的强制出栈、以及日志乱序版的排序防御。把这三个变体想清楚这道题才算真正吃透了。
如果你刷过 LeetCode应该见过这道题636. Exclusive Time of Functions中文一般叫“函数的独占时间”。光看名字可能觉得是个数学题其实是典型的“日志还原 栈模拟”问题在面试里出现频率不低尤其是在考察候选人对调用栈和状态机理解是否扎实的时候。我第一次遇到这题时还以为是时间线合并结果越做越觉得趣味性很强——它表面在算时间实际是在还原一段单线程 CPU 的执行现场把一段段中断、嵌套、返回的过程用栈老老实实拼回去。这篇内容我尽量把思路、代码、边界情况、实际应用讲透适合刚开始刷题的同学也适合想系统地理解栈模拟问题的朋友。这题给我们的输入很简单一个整数n代表有n个函数编号从0到n-1一个字符串数组logs里面每一个元素长这样id:start:timestamp或id:end:timestamp。它模拟的是单线程 CPU 上函数的调用和返回日志要我们算出每一个函数实际独占 CPU 的总时间。这里有个特别关键的点在单线程环境下同一时刻只有一个函数在执行其他函数都处于“被挂起但还没结束”的状态而题目要的就是去掉所有子函数占用时间之后真正属于这个函数自己的那部分时间。听起来像递归回溯其实完全可以用一个栈轻松解决。我从拿到题目到真正理解它的过程踩了不少坑也总结了一套可以直接复用的解题套路。这篇文章会尽量用我自己的实操视角来讲不整那些太虚的理论核心就是把状态机和栈的细节掰开揉碎。1. 题目到底在讲什么一个单线程 CPU 的“时间账本”1.1 输入结构和基本规则先把规则说清楚。logs里每条日志只可能是两种格式id:start:timestamp表示函数id在timestamp这一毫秒开始执行。id:end:timestamp表示函数id在timestamp这一毫秒执行结束。这里有一个特别容易搞混的细节日志里的时间戳指的是“毫秒单位”而且一个函数的执行区间是闭区间。比如0:start:0和0:end:0表示函数 0 在第 0 毫秒开始也在第 0 毫秒结束它独占的时间不是 0而是 1。很多人在第一步就栽在这里。题目本身是假设日志按时间顺序给出的但我在实际面试和工程里见过不少日志乱序的情况所以一会儿我会把乱序的处理也加进去。打个比方这就像公司里的工位监控摄像头谁在哪个工位上干活什么时候坐下什么时候离开都有一条记录。单线程 CPU 就是只有一张工位同时只可能有一个人坐着干活。start就是“有人坐下”end就是“有人离开”我们要算的是每个人真正坐在工位上干活的总时长中途被叫走去开会也就是嵌套调用子函数的时间不能算在他头上。1.2 为什么栈是天然的数据结构调用栈本身就是后进先出。函数 A 开始然后 A 调用了 B再然后 B 调用了 C那结束的时候一定是 C 先结束再 B 结束最后 A 结束。这就决定了我们不需要什么东西来排序或回溯一个栈就足够。栈顶永远都是当前正在执行的那个函数而栈里剩下的函数都是“已经被调用但还没返回”的挂起状态。我之前试过用数组记录每个函数的累计时间再用一个 flag 标记当前函数结果遇到嵌套调用直接乱套因为函数 A 被 B 打断之后还得恢复恢复后可能又被 C 打断光靠一个 flag 根本记不住“上一任是谁”。从那时候起我就深刻理解了解决这种嵌套结构栈不是一种选择而是唯一优雅的解法。2. 思路拆解时间区间切割与栈的配合2.1 核心思想把每一毫秒都“记到账”上要理解这道题的做法最直观的办法是别把日志看成一整段时间而是看成若干小段每一小段都要有一个归属。当start事件发生时发生了一次“当前函数切换”之前正在运行的函数会暂停从暂停那一刻起一直到新函数开始这段时间仍然属于旧函数。当end事件发生时当前函数结束从该函数最近一次拿到 CPU 到结束的这段区间全部属于这个被结束的函数然后栈回退到上一层函数。所以我们要维护两个东西一个栈用来存放“已经开始且尚未结束”的函数 id栈顶就是当前正在执行的函数。一个prev变量表示“上一个事件发生的时间点”更准确地说是上一个时间账已经结清的时刻。每次遇到start如果当前栈不为空说明旧函数被中断了那么旧函数从prev到timestamp - 1这一整段都是它的独占时间要加起来。新函数入栈。prev timestamp。每次遇到end栈顶函数从prev到timestamp的整个闭区间都是它的独占时间也就是timestamp - prev 1加给它。弹出栈顶。prev timestamp 1。这里最微妙的地方就是prev的更新时机。start之后把prev更新为timestamp是因为新函数从这个毫秒开始真正占用 CPUend之后把prev更新为timestamp 1是因为这个函数在这个毫秒结束下一秒开始才可能轮到别人。用闭区间的视角来看prev始终指向“当前还没有被记账的一个时间点”。这是整个算法里最关键的设计我每写一步都会下意识检查prev到底指向哪儿一旦状态混乱答案必然错。2.2 完整示例模拟一行日志一行账拿题目的示例来手动过一遍。假设n 2日志如下0:start:0 1:start:2 1:end:5 0:end:6初始ans [0, 0]stack []prev 0。处理0:start:0栈空不累加函数 0 入栈。stack [0]prev 0。处理1:start:2栈顶是 0把2 - 0 2累加到ans[0]函数 1 入栈。此时ans [2, 0]stack [0, 1]prev 2。处理1:end:5栈顶是 1把5 - 2 1 4累加到ans[1]弹出函数 1。此时ans [2, 4]stack [0]prev 6。处理0:end:6栈顶是 0把6 - 6 1 1累加到ans[0]弹出函数 0。最终ans [3, 4]。手动模拟一遍就会发现整个过程就像在用一把尺子量一段段不重叠的时间区间然后贴标签归档。函数 0 的总时间 3 最开始的 2 毫秒加上最后收尾的 1 毫秒中间完全被函数 1 拿走的 4 毫秒被精准地排除在外了。2.3 关于“时间区间”的深层理解如果把日志可视化到时间轴上你会发现整段时间被所有start和end切成了很多小碎片。每个碎片要么属于栈顶的那个函数要么属于新来的那个函数不存在“空转”的时间也不存在一个碎片同时属于两个函数的情况。这正是这个算法的正确性来源。我还试过另一种思路先计算出每个函数的[start, end]区间再把子函数的区间从父函数里扣掉。理论上可行但实现起来复杂得多因为要处理多个子函数区间合并、嵌套层级以及区间重叠远不如栈这个方案简洁。所以栈 时间点对齐这套组合本质是在做“差分记账”一次遍历就把所有函数的累计时间算完不需要回溯也不需要反复扫描。3. 完整实现代码从想法到落地3.1 标准解法Python先把最标准的实现贴出来我加了乱序防御的排序环节from typing import List def exclusiveTime(n: int, logs: List[str]) - List[int]: ans [0] * n stack [] prev 0 # 防御性处理如果日志不是严格按时间递增先按时间戳排序 logs sorted(logs, keylambda x: int(x.split(:)[2])) for log in logs: parts log.split(:) fid int(parts[0]) typ parts[1] timestamp int(parts[2]) if typ start: if stack: ans[stack[-1]] timestamp - prev stack.append(fid) prev timestamp else: # end 事件 ans[stack.pop()] timestamp - prev 1 prev timestamp 1 return ans这个代码我实测过配合 LeetCode 的logs输入能直接通过。核心逻辑就这几行但如果没想清楚面试时很容易在end分支的1和prev的更新上出 bug。3.2 几个关键细节的再解释为什么start时不加1start事件发生时旧函数被中断但从旧函数拿到 CPU 到新函数开始之间最多只有timestamp - prev毫秒。注意如果timestamp prev就说明旧函数刚在同一毫秒被中断它在这个毫秒没有额外占用时间因为这一毫秒的开头和结尾重叠了所以不加1。而end事件不一样它代表函数持续到了这个毫秒闭区间所以是timestamp - prev 1。为什么end之后prev timestamp 1因为end所在的这一毫秒已经被当前函数消耗完了。下一个日志无论它是start还是end最早也只能从timestamp 1开始计算。如果忘记改成1下一个start会把已经属于上一个函数的时间重复叠加到新函数头上。为什么栈里存放的是函数 id而不需要额外存时间因为每个函数从入栈到出栈这段时间里到底被分配了多少个时间碎片是通过每次扫描事件时逐步累加进去的不需要等到出栈时再回头算总账。栈只维护嵌套关系时间细节全部由prev承担。乱序日志的排序处理题目默认logs是按时间排序的但真实场景里日志可能来自多个线程缓冲并不保证严格有序。排序本身是O(m log m)m是日志条数虽然比一遍扫描慢但对工程上的鲁棒性帮助很大。如果面试官强调输入必然有序那就可以省掉排序保持O(m)的时间复杂度。3.3 其他语言实现Java / C 简版我自己面试时常用 Java 写所以也给出一个 Java 版本供参考public int[] exclusiveTime(int n, ListString logs) { int[] ans new int[n]; DequeInteger stack new ArrayDeque(); int prev 0; for (String log : logs) { String[] parts log.split(:); int fid Integer.parseInt(parts[0]); String type parts[1]; int ts Integer.parseInt(parts[2]); if (start.equals(type)) { if (!stack.isEmpty()) { ans[stack.peek()] ts - prev; } stack.push(fid); prev ts; } else { int id stack.pop(); ans[id] ts - prev 1; prev ts 1; } } return ans; }C 版本也差不多但要注意std::stack的top()和pop()是分开的别在弹出后才取值。vectorint exclusiveTime(int n, vectorstring logs) { vectorint ans(n, 0); stackint st; int prev 0; for (const string log : logs) { int pos1 log.find(:); int pos2 log.rfind(:); int id stoi(log.substr(0, pos1)); string type log.substr(pos1 1, pos2 - pos1 - 1); int ts stoi(log.substr(pos2 1)); if (type start) { if (!st.empty()) ans[st.top()] ts - prev; st.push(id); prev ts; } else { ans[st.top()] ts - prev 1; st.pop(); prev ts 1; } } return ans; }4. 边界条件和易踩的坑只有实际跑过才知道4.1 高频踩坑点汇总我刷题时第一版代码在“函数 0 结束后的prev更新”上翻过车后来把几个高频错误整理成了清单团队新人问我的时候我也直接甩给他们对照常见错误错误表现正确做法忘记end的1所有函数的时间都少算变为timestamp - prev 1start时也加1函数时间多算一毫秒追加区间长度是timestamp - prev弹出栈顶前没累加子函数时间丢失必须在pop()前用栈顶 id 更新ans乱序日志未排序结果全错且出错找不到原因时间戳排序或确认输入有序栈空时处理end空栈调用pop()抛异常正常情况下日志合法不乱序不会出现防御上可先判空prev没有及时更新时间重叠或漏算每次事件结束后都要同步prev4.2 边界场景的实测我自己在空日志和单函数场景下跑过n 1, logs []返回[0]。代码里ans [0]栈为空直接返回没问题。n 1, logs [0:start:0, 0:end:0]start时不加区间end时0 - 0 1 1返回[1]符合预期。n 2, logs [0:start:0, 0:start:1, 0:end:2, 0:end:3]同一个函数递归调用自己。第一次start把函数 0 入栈第二次start又入栈一次实际上就是函数 0 递归调用了自己。结束后两次end分别出栈最终答案应该覆盖整个 0 到 3 的区间没问题。连续end的场景比如0:start:0、1:start:1、1:end:2、0:end:2。最后一次end的timestamp 2但函数 0 之前被中断时prev已经变成 2所以函数 0 在最后这毫秒只能分到2 - 2 1 1正好是一个收尾毫秒。这里如果prev被错误地更新为3就会导致函数 0 多出 1 毫秒。实测下来我对这个细节格外敏感。4.3 如果输入不合法怎么办题目承诺日志合法但工程上日志可能因为崩溃或数据采集异常而出现end没有对应start、函数编号越界等情况。我在做防御性编码时会加一些保护逻辑比如在end分支里先判断栈是否为空空则跳过栈顶函数 id 是否在0..n-1范围内不在则不统计。这样刷题时可以更从容地应对输入变体也符合实际工程里“绝不因为一条脏数据挂掉整个服务”的原则。5. 复杂度分析和优化方向5.1 时间和空间复杂度先看标准解法。遍历一次logs每条日志做常数次操作所以时间复杂度是O(m)其中m是日志条数如果加了排序则是O(m log m)。空间方面栈最多存放所有嵌套调用的函数 id理论上深度等于嵌套层数最坏情况下所有函数都同时嵌套栈大小为O(n)ans数组大小为O(n)所以总的空间复杂度为O(n)。在面试时我会把这几点说清楚遍历一次日志是必须的因为每个时间戳都会被算进某个函数栈的大小不会超过函数总数因为每个函数 id 最多同时出现在栈里一次。当然递归调用自身的场景下同一个函数 id 会入栈多次但函数数量上限仍然是n栈深度也不可能超过日志条数。5.2 能不能优化成不用栈我试过不用栈的“区间合并”思路先算出每个函数的[start, end]区间再合并所有子函数区间最后从父函数区间里扣掉。但问题是嵌套层级使得“父函数”和“子函数”的关系不好从扁平数组里恢复必须额外构建树或反复扫描时间和空间上都不如栈来得干净。所以这个问题的标准答案就应该是栈没有更简单的路。如果日志已经有序那还可以考虑“事件指针”的方式按时间轴扫描事件本质上还是在模拟栈只是把栈藏进了事件指针里不适合推广。6. 从算法题到实际工程函数独占时间到底有什么用6.1 性能剖析器和 APM 工具里的影子不要觉得这题只是面试造火箭。很多性能剖析工具profiler的核心逻辑就是在计算“某个函数在 CPU 上真实执行的时间”排除掉它内部调用其他函数的时间。比如 Node.js 的--prof日志、Java 的 JFR 事件、Python 的cProfile它们内部都会有类似“函数进入/退出事件”的数据流最终要回答的问题和 LeetCode 636 完全一致每个函数自己花了多少 CPU 时间。我早年写过一个简易的耗时打点系统当时就把每个接口的start:end日志喂给一个栈模型计算出每个中间件、每个数据库调用的独占时长。这和 LeetCode 636 的区别只是日志不是id:start:timestamp这种文本而是结构化的时间戳字段算法骨架一模一样。所以刷这道题对做性能分析工具的人是有直接帮助的。6.2 并发和多线程下的扩展思考如果把单线程扩展为多线程问题会从“同一时刻只有一个函数在执行”变成“同一时刻有多个线程各自执行自己的函数”这时就不能用单个栈了而是要按线程 ID 分桶每个线程维护一个独立的调用栈再把每个线程内算出的独占时间汇总到全局函数维度。很多企业级 APM 系统就是这么设计的核心思想仍然是“栈模拟 区间记账”。如果是抢占式调度一个线程中途被 CPU 切换出去虽然操作系统层面会记录上下文切换但在应用层看到的日志仍然只有start和end所以算法层面不需要额外处理。如果日志里有中断、异常等事件那就要考虑“当前函数被强制终止”的情况栈顶可能不是正常end弹出而是被异常事件强制清空这时候就要额外定义被异常打断的函数独占时间算到哪个时间点。这些工程化的扩展非常有意思也说明一个简单的算法题可以延伸到很深的地方。7. 常见问题速查与小技巧7.1 我在面试和自我练习时的问答问为什么end时间戳对应的毫秒算在函数身上答因为日志是用闭区间语义表达的end所在的这一毫秒函数仍然在 CPU 上执行。这在题目描述里没有直接写但通过示例可以确定。如果题目改成半开区间那结束毫秒就不算了代码要相应调整。问如果两个事件时间戳相同比如0:start:5、1:start:5怎么处理答按输入顺序处理。先处理0:start:5函数 0 入栈prev 5再处理1:start:5栈顶函数 0 累加5 - 5 0然后函数 1 入栈。这样函数 0 在同一毫秒被中断没有额外时间符合逻辑。实际系统的日志一般不会出现同一函数同一毫秒 start 多次但同一毫秒不同函数 start 是可能的顺序约定很重要。问如果日志条数很多怎么优化答避免使用split以外的额外字符串操作解析时直接定位冒号位置如果用 C建议直接遍历字符串而不是反复substr。排序可以省则省因为题目保证有序。如果对内存有要求可以把logs原地解析成结构体数组再处理减少字符串分割开销。7.2 一个实用的小技巧手动模拟调试如果在本地写代码遇到结果不对我的习惯是写一个十分简单的调试函数把栈状态和ans在每一轮打印出来肉眼核对。比如def debug_exclusiveTime(n, logs): ans [0] * n stack [] prev 0 for log in logs: parts log.split(:) fid, typ, ts int(parts[0]), parts[1], int(parts[2]) if typ start: if stack: ans[stack[-1]] ts - prev stack.append(fid) prev ts else: ans[stack.pop()] ts - prev 1 prev ts 1 print(flog{log}, stack{stack}, ans{ans}, prev{prev}) return ans每一步都看清楚就能快速定位是prev还是加减 1 的问题。这个“打印状态机”的调试方式不仅适用于这题几乎所有日志解析类题目都可以用。7.3 几个我常提醒自己的小点一定要先想清楚区间是闭区间还是半开区间不同题目定义不同。入栈时栈顶函数的时间累加用的是timestamp - prev不是timestamp也不是timestamp 1。出栈时补上1是因为闭区间的结束毫秒。如果题目改成开区间这里就变成timestamp - prev。函数 id 可能很大但不会超过n - 1如果有负数 id属于非法输入防御式代码可以直接忽略。这道题其实没有特别高深的算法高级数据结构也没用到但非常考验对状态转换的理解。说白了就是一组事件流栈负责保存现场prev负责维护结算边界二者配合就能完美还原所有函数的独占时间。我个人在实际操作中的体会是这类题不要一上来就套模板先拿小例子手动走一遍画出时间和函数切换的时间轴再抽象成状态机代码就水到渠成了。后面刷到类似的“日志还原类”题目时你会发现这套“栈 时间边界”组合几乎能直接迁移过去。如果你正在准备面试建议把这道题的三个变体也顺手想想多线程版的按线程分桶、带异常中断版的强制出栈、以及日志乱序版的排序防御。把这三个变体想清楚这道题才算真正吃透了。
