接手线上系统那天我对着几千行函数进出日志算了整整一个下午发现所有函数的耗时加起来比接口总耗时还多出一大截。后来才反应过来问题出在“嵌套调用”——子函数跑的时间被父函数重复算了一遍。这个场景你只要做过性能分析就一定遇到过而 LeetCode 上那道“函数的独占时间”题本质就是在解决这个真实痛点。这篇文章不打算只讲答案我会把题面的隐藏规则、栈解法的底层逻辑、边界条件以及怎么把它迁移到真实项目的调用耗时分析里一次性说清楚。1. 这道题到底在解决什么现实问题1.1 一个日志排障场景想象一下你负责的下单接口最近频繁超时你在代码里埋了性能日志每个函数进入和退出时都会打一条带时间戳的记录。日志大概长这样0:start:0 1:start:2 1:end:5 0:end:6每条日志的格式是函数ID:事件类型:时间戳start表示函数开始执行end表示函数结束。现在的需求是算出每个函数“自己真正执行”的时间不包含它调用子函数的时间。如果只有单个函数这个统计很简单。一旦出现嵌套调用——函数0调用了函数1函数1又调用了函数2——很多人就会算错。最常见的错误是把整个时间段都记到父函数头上导致父函数耗时虚高、子函数耗时也虚高加起来远远超过总耗时。这正是我当初线上踩坑的根源。1.2 为什么“嵌套调用”会算错时间先看一组最简单的例子0:start:0 0:end:4一眼就能看出函数0耗时4个单位。但如果中间插入子函数调用问题就来了0:start:0 1:start:1 1:end:3 0:end:4函数0从时刻0跑到时刻4共4个单位函数1从时刻1跑到时刻3共2个单位。可如果直接“外层减内层”函数0耗时 (4 - 0) - (3 - 1) 2个单位函数1耗时 2个单位加起来倒是4。这个算法在单层嵌套下还能算对一旦多层嵌套、平级调用混合在一起光靠“外层减内层”就很容易乱。原因在于你不知道某个子函数是在哪个父函数内部被调用的也不知道同一层级的多个函数之间怎么切分时间。1.3 什么人需要掌握这道题如果你正准备算法面试这道题是“栈”类型里非常经典的一道几乎必刷如果你在做后端性能优化、APM应用性能监控系统、日志分析工具这道题的思路可以直接复用。它不算难但特别能考察一个人对“时间区间”和“调用栈模型”的理解是否清晰。我后面会从题面细节开始讲到代码实现最后延展到工程场景保证你看完能直接上手。2. 题面逐字拆解日志格式、时间戳约定与隐藏规则2.1 输入和输出长什么样题目会给两个参数一个是函数总数n另一个是日志数组logs。函数ID从0到n-1每一条日志都满足id:start:时间戳或id:end:时间戳的格式。要求返回一个长度为n的数组ans[i]表示第i个函数的独占时间。标准示例输入: n 2, logs [0:start:0, 1:start:2, 1:end:5, 0:end:6] 输出: [3, 4]很多第一次做这道题的人会卡在这个示例上函数0明明从0到6为什么输出是3而不是4或者6因为函数0在执行到时刻2时被函数1打断函数1结束后它又继续跑所以函数0真正执行的时间是[0,2)加上[5,6]也就是3个单位。函数1从时刻2跑到时刻5注意它占用的单位是2、3、4、5共4个单位。2.2 start和end的时间戳到底怎么算这是全网讨论最多、也是出错率最高的一个细节。题目里并没有用大白话告诉你但通过示例可以推导出如下约定start:ts表示函数从时刻ts开始占用CPUts这个时间点本身不产生执行时间执行从ts之后才算。end:ts表示函数在时刻ts结束ts这个时间点本身属于该函数要计入执行时间。所以对于0:start:0和0:end:6start在时刻0执行区间可以理解为[0, 1)开始的第一格但“0”这个点不单独计入end在时刻6执行区间是(...6]“6”这个点要计入。你会发现如果用“半开区间”来理解start是左闭右开end也是左闭右开但两者的右端点归属不同。这也是为什么代码里end事件累加时要写成ts - prev 1而start事件累加时是ts - prev。2.3 题目没说但你必须知道的约定LeetCode的原始题目保证logs是合法调用序列也就是说start和end成对出现且不会出现“结束一个还没开始的函数”这种非法情况。但题目没有明说的另一些约定同样重要日志列表已经按时间顺序排好不需要你排序。同一个函数可以多次入栈典型场景是递归调用。时间戳的范围可能很大但Java的int足够容纳不必用long。事件类型只有start和end两种不存在第三种状态。这些约定决定了整个实现可以非常干净不需要处理日志乱序等复杂情况。不过我在第6节会讲真实工程日志往往没那么守规矩到时候再做变体扩展。3. 为什么栈是唯一合适的解法3.1 函数调用天然满足“后进先出”函数调用和括号匹配本质上是同一个模型函数A开始函数A内部调用BB开始B结束然后A才能继续执行。这完全符合栈的后进先出特性。你只需要维护一个“当前正在运行的函数栈”栈顶就是此刻正在CPU上执行的那个函数。为什么不能用哈希表因为哈希表只能记录“某个函数有没有在执行”却无法表达“谁在谁里面执行”。函数的嵌套关系是严格的树形结构只有栈能保存这个层级关系。为什么不能用数组模拟数组也能伪造一个“栈指针”本质上还是栈没必要绕弯子。3.2 模拟一次完整的日志回放拿前面的标准示例手推一遍logs [0:start:0, 1:start:2, 1:end:5, 0:end:6]初始栈为空prev 0。第一条0:start:0栈为空没有需要累加的旧函数。把0入栈prev 0。 此时栈内状态[0]函数0开始执行。第二条1:start:2当前栈顶是0说明函数0从时刻prev0到时刻2执行了2个单位把这2个单位累加到函数0上。接着把1入栈prev 2。 此时栈内状态[0, 1]函数1开始执行。第三条1:end:5栈顶是1说明函数1从时刻prev2到时刻5执行了4个单位2、3、4、5累加到函数1上。把1弹出栈prev 5 1 6。 此时栈内状态[0]函数0恢复执行。第四条0:end:6栈顶是0说明函数0从时刻prev6到时刻6执行了1个单位只有6这个点累加到函数0上。把0弹出栈prev 7。最终结果函数0 2 1 3函数1 4。这里有个关键点每次end之后prev要更新为ts 1不是ts。因为ts这个时刻已经被当前函数消耗掉了下一个事件无论是什么都应该从ts 1开始计时。3.3 为什么不能用“全局时间相减”替代栈有人会问能不能统计出每个函数从start到end的总时长再减去它所有子函数的总时长剩下的就是独占时间理论上可以但实现起来比栈麻烦得多对于同一个函数多次递归调用你需要区分“哪一次start对应哪一次end”对平级函数的间隔时间归属需要明确知道当前父函数是谁最麻烦的是你需要额外维护一个“孩子时间累计”的哈希表每次子函数结束时要把时间加到父函数的“被占用时间”里。这套逻辑本质上还是在模拟一个调用栈只是更绕。栈解法把所有信息都保存在运行时状态中代码更短、更不容易出错。4. 代码实现一版能直接跑的Java解法附Python对照4.1 Java实现与逐行解析public int[] exclusiveTime(int n, ListString logs) { int[] res new int[n]; DequeInteger stack new ArrayDeque(); int prev 0; for (String log : logs) { String[] parts log.split(:); int id Integer.parseInt(parts[0]); String type parts[1]; int ts Integer.parseInt(parts[2]); if (start.equals(type)) { if (!stack.isEmpty()) { res[stack.peek()] ts - prev; } stack.push(id); prev ts; } else { // 题目保证合法栈顶一定是当前结束的函数 int endedId stack.pop(); res[endedId] ts - prev 1; prev ts 1; } } return res; }逐行说明res数组保存每个函数的独占时间初始全为0。DequeInteger stack用双端队列当栈用这里用ArrayDeque比Stack性能更好也符合现代Java实践。prev表示“上一次事件发生的时间点”它是整个算法的灵魂。遇到start时先给栈顶函数结算一段“从prev到现在”的时间再把新函数压栈。注意这里是peek不是pop因为栈顶函数还没结束只是被新函数打断了。遇到end时栈顶函数必然是要结束的函数给它结算ts - prev 1然后弹出。prev更新为ts 1因为ts这一格已经被结束函数占用了。4.2 Python实现对照如果你平时用Python写算法题下面这个版本可以直接背def exclusiveTime(n: int, logs: List[str]) - List[int]: res [0] * n stack [] prev 0 for log in logs: parts log.split(:) fid int(parts[0]) typ parts[1] ts int(parts[2]) if typ start: if stack: res[stack[-1]] ts - prev stack.append(fid) prev ts else: fid stack.pop() res[fid] ts - prev 1 prev ts 1 return resPython的list自带append和pop天然就是栈。注意log.split(:)返回的是字符串列表int()转换别漏。4.3 复杂度与内存分析时间复杂度O(m)其中m是日志条数。每条日志只处理一次入栈出栈都是O(1)整体线性。空间复杂度O(n)栈中最坏情况下会同时存在n个函数比如函数0调用函数1函数1再调用函数2一直到函数n-1res数组也是O(n)。这个复杂度已经是理论下界了因为你必须至少扫描一遍所有日志才有办法统计时间不可能做到O(log n)之类的对数复杂度。5. 最容易踩坑的4个细节从提交记录里捞出的真实经验5.1 end事件为什么必须“1”这是这道题最大的坑没有之一。很多人写完代码信心满满地提交结果发现示例都没过。原因在于start事件累加时用的是ts - prev但end事件累加用的是ts - prev 1。为什么不是对称的因为两个事件的时间戳语义不同。start:2意味着从时刻2开始时刻2本身不算执行时间end:5意味着在时刻5结束时刻5本身算执行时间。等价于说函数从时间2开始执行了时间2、3、4、5共4个单位。如果按照ts - prev只能算到3个单位把5漏掉了。一个辅助记忆技巧遇到end时时间戳对应的那一格是“最后执行的一格”必须计入遇到start时那个时刻属于“上一段区间的终点”不属于新函数。工程上你也可以理解成end是“左闭右闭区间的右端点”start是“左闭右开区间的左端点”。5.2 prev变量比当前时间戳更关键代码里有个很容易被忽略的细节prev并不是简单等于“上一条日志时间戳”而是“上一个事件处理完之后时间的下边界”。在start事件里prev ts在end事件里prev ts 1。这个1极其重要。假设有一段日志0:start:0 0:end:1 1:start:2 1:end:3如果end之后把prev错误地设为ts那么处理1:start:2时会发现ts - prev 0看似没问题但再往下处理1:end:3时3 - 2 1 2函数1被算成2个单位实际上它只执行了1个单位。所以prev必须代表“下一个可分配时间片的起点”而不是简单的时间戳。5.3 递归调用和同id重复入栈递归调用时同一个函数ID会在栈里出现多次。比如0:start:0 0:start:1 0:end:2 0:end:3这条日志对应函数0的两次递归调用第一次调用从0开始在1时调用了自己第二次从1执行到2结束然后第一次调用从2继续到3结束。用栈处理时栈里会出现两个0这是完全正常的。遇到end:2时弹出的应该是栈顶那个0遇到end:3时弹的是下面那个0。二者累加的时间分别是2-112和3-212共4个单位正好是总时间。有些同学遇到重复ID就害怕觉得哈希表会覆盖其实栈天然支持重复元素不需要做任何特殊处理。5.4 日志合法性的边界处理LeetCode的原题保证日志合法但真实面试和工程项目里这个假设不一定成立。常见的边界情况空日志直接返回全0数组代码自然支持因为循环体不会执行。日志不合法比如出现了0:end:5但没有对应的start此时stack.pop()会抛出异常。如果要做防御性编程可以在end时检查栈是否为空或者判断栈顶是否等于当前id。同一个时间戳多个事件理论上是允许的。比如0:end:5和1:start:5放一起只要日志顺序正确就没问题。由于end会把prev设为ts1后面start的ts-prev可能是负数——不过在合法序列里不会出现这种情况因为不可能在函数0结束的同一时刻开启一个本应在它之前执行的函数。函数ID不在0到n-1之间原题不会出现但真实数据里日志可能来自未埋点的第三方库建议过滤。6. 从题目到工程用同样的思路实现真实调用耗时分析6.1 实战变体日志不保证有序怎么办真实系统的日志往往是多线程并发写的落盘顺序可能和实际发生顺序不一致。如果日志没排序直接套上面的解法会得到错误结果因为start和end的顺序被打乱了。简单的处理方案是先按时间戳排序。但要小心同一时间戳下start和end的相对顺序会影响嵌套关系。一个比较稳的做法是按(时间戳, 事件类型优先级)排序约定同一时刻end排在start前面或者反过来并在日志ID里加上全局自增序号来保证同时间戳事件的原始顺序。更稳妥的方案是改造埋点层给每条日志打上进程内单调递增的序列号按“时间戳序列号”双字段排序这样能还原出真实的调用顺序。6.2 实战变体多线程下多组调用栈真实分布式系统日志里通常带线程ID不同线程的调用栈是互相独立的。你不能把所有线程的日志混进同一个栈里算否则一个线程的函数A还没结束另一个线程的函数B就把栈顶抢了。解法是维护一个Map线程ID, Deque函数ID每个线程一个栈每个线程还要维护一个独立的prev。为了减少内存占用可以只维护“活跃线程”的栈线程结束后清理掉。基本逻辑和单栈解法一模一样只是多了一层按线程分组。6.3 从独占时间到Span自耗时统计如果你接触过分布式链路追踪系统比如Jaeger、SkyWalking、Zipkin会发现“Span的self_time”和“函数独占时间”本质上是同一个概念。一个Span代表一次调用它可能有多个子Span它的self_time等于Span总耗时 - 所有子Span耗时之和。在实现里你可以用一棵调用树来表达整个调用链每个节点记录自己的开始时间、结束时间、子节点列表。后序遍历这棵树就能算出每个节点的self_time。这比用栈更直观但代价是内存占用更高因为你要先构建完整调用树才能统计。栈解法的优势是单次扫描即出结果适合日志规模特别大的场景。我后来在组里做过一个内部工具就是把这道题的思路封装成纯流式处理器日志逐行读入遇到start就临时挂起父函数遇到end就结算当前函数。线上几百万条日志跑下来内存占用稳定在几十MB以内比先构建全量调用树再统计的方案轻量得多。最后再分享一个小技巧面试时如果你的解法里用到了prev ts 1面试官基本能一眼看出你真正理解了这道题。你可以主动解释end时间戳包含在该函数耗时内所以下一个事件要从ts1开始计时。这一句话通常比闷头写代码加分更多。
接手线上系统那天我对着几千行函数进出日志算了整整一个下午发现所有函数的耗时加起来比接口总耗时还多出一大截。后来才反应过来问题出在“嵌套调用”——子函数跑的时间被父函数重复算了一遍。这个场景你只要做过性能分析就一定遇到过而 LeetCode 上那道“函数的独占时间”题本质就是在解决这个真实痛点。这篇文章不打算只讲答案我会把题面的隐藏规则、栈解法的底层逻辑、边界条件以及怎么把它迁移到真实项目的调用耗时分析里一次性说清楚。1. 这道题到底在解决什么现实问题1.1 一个日志排障场景想象一下你负责的下单接口最近频繁超时你在代码里埋了性能日志每个函数进入和退出时都会打一条带时间戳的记录。日志大概长这样0:start:0 1:start:2 1:end:5 0:end:6每条日志的格式是函数ID:事件类型:时间戳start表示函数开始执行end表示函数结束。现在的需求是算出每个函数“自己真正执行”的时间不包含它调用子函数的时间。如果只有单个函数这个统计很简单。一旦出现嵌套调用——函数0调用了函数1函数1又调用了函数2——很多人就会算错。最常见的错误是把整个时间段都记到父函数头上导致父函数耗时虚高、子函数耗时也虚高加起来远远超过总耗时。这正是我当初线上踩坑的根源。1.2 为什么“嵌套调用”会算错时间先看一组最简单的例子0:start:0 0:end:4一眼就能看出函数0耗时4个单位。但如果中间插入子函数调用问题就来了0:start:0 1:start:1 1:end:3 0:end:4函数0从时刻0跑到时刻4共4个单位函数1从时刻1跑到时刻3共2个单位。可如果直接“外层减内层”函数0耗时 (4 - 0) - (3 - 1) 2个单位函数1耗时 2个单位加起来倒是4。这个算法在单层嵌套下还能算对一旦多层嵌套、平级调用混合在一起光靠“外层减内层”就很容易乱。原因在于你不知道某个子函数是在哪个父函数内部被调用的也不知道同一层级的多个函数之间怎么切分时间。1.3 什么人需要掌握这道题如果你正准备算法面试这道题是“栈”类型里非常经典的一道几乎必刷如果你在做后端性能优化、APM应用性能监控系统、日志分析工具这道题的思路可以直接复用。它不算难但特别能考察一个人对“时间区间”和“调用栈模型”的理解是否清晰。我后面会从题面细节开始讲到代码实现最后延展到工程场景保证你看完能直接上手。2. 题面逐字拆解日志格式、时间戳约定与隐藏规则2.1 输入和输出长什么样题目会给两个参数一个是函数总数n另一个是日志数组logs。函数ID从0到n-1每一条日志都满足id:start:时间戳或id:end:时间戳的格式。要求返回一个长度为n的数组ans[i]表示第i个函数的独占时间。标准示例输入: n 2, logs [0:start:0, 1:start:2, 1:end:5, 0:end:6] 输出: [3, 4]很多第一次做这道题的人会卡在这个示例上函数0明明从0到6为什么输出是3而不是4或者6因为函数0在执行到时刻2时被函数1打断函数1结束后它又继续跑所以函数0真正执行的时间是[0,2)加上[5,6]也就是3个单位。函数1从时刻2跑到时刻5注意它占用的单位是2、3、4、5共4个单位。2.2 start和end的时间戳到底怎么算这是全网讨论最多、也是出错率最高的一个细节。题目里并没有用大白话告诉你但通过示例可以推导出如下约定start:ts表示函数从时刻ts开始占用CPUts这个时间点本身不产生执行时间执行从ts之后才算。end:ts表示函数在时刻ts结束ts这个时间点本身属于该函数要计入执行时间。所以对于0:start:0和0:end:6start在时刻0执行区间可以理解为[0, 1)开始的第一格但“0”这个点不单独计入end在时刻6执行区间是(...6]“6”这个点要计入。你会发现如果用“半开区间”来理解start是左闭右开end也是左闭右开但两者的右端点归属不同。这也是为什么代码里end事件累加时要写成ts - prev 1而start事件累加时是ts - prev。2.3 题目没说但你必须知道的约定LeetCode的原始题目保证logs是合法调用序列也就是说start和end成对出现且不会出现“结束一个还没开始的函数”这种非法情况。但题目没有明说的另一些约定同样重要日志列表已经按时间顺序排好不需要你排序。同一个函数可以多次入栈典型场景是递归调用。时间戳的范围可能很大但Java的int足够容纳不必用long。事件类型只有start和end两种不存在第三种状态。这些约定决定了整个实现可以非常干净不需要处理日志乱序等复杂情况。不过我在第6节会讲真实工程日志往往没那么守规矩到时候再做变体扩展。3. 为什么栈是唯一合适的解法3.1 函数调用天然满足“后进先出”函数调用和括号匹配本质上是同一个模型函数A开始函数A内部调用BB开始B结束然后A才能继续执行。这完全符合栈的后进先出特性。你只需要维护一个“当前正在运行的函数栈”栈顶就是此刻正在CPU上执行的那个函数。为什么不能用哈希表因为哈希表只能记录“某个函数有没有在执行”却无法表达“谁在谁里面执行”。函数的嵌套关系是严格的树形结构只有栈能保存这个层级关系。为什么不能用数组模拟数组也能伪造一个“栈指针”本质上还是栈没必要绕弯子。3.2 模拟一次完整的日志回放拿前面的标准示例手推一遍logs [0:start:0, 1:start:2, 1:end:5, 0:end:6]初始栈为空prev 0。第一条0:start:0栈为空没有需要累加的旧函数。把0入栈prev 0。 此时栈内状态[0]函数0开始执行。第二条1:start:2当前栈顶是0说明函数0从时刻prev0到时刻2执行了2个单位把这2个单位累加到函数0上。接着把1入栈prev 2。 此时栈内状态[0, 1]函数1开始执行。第三条1:end:5栈顶是1说明函数1从时刻prev2到时刻5执行了4个单位2、3、4、5累加到函数1上。把1弹出栈prev 5 1 6。 此时栈内状态[0]函数0恢复执行。第四条0:end:6栈顶是0说明函数0从时刻prev6到时刻6执行了1个单位只有6这个点累加到函数0上。把0弹出栈prev 7。最终结果函数0 2 1 3函数1 4。这里有个关键点每次end之后prev要更新为ts 1不是ts。因为ts这个时刻已经被当前函数消耗掉了下一个事件无论是什么都应该从ts 1开始计时。3.3 为什么不能用“全局时间相减”替代栈有人会问能不能统计出每个函数从start到end的总时长再减去它所有子函数的总时长剩下的就是独占时间理论上可以但实现起来比栈麻烦得多对于同一个函数多次递归调用你需要区分“哪一次start对应哪一次end”对平级函数的间隔时间归属需要明确知道当前父函数是谁最麻烦的是你需要额外维护一个“孩子时间累计”的哈希表每次子函数结束时要把时间加到父函数的“被占用时间”里。这套逻辑本质上还是在模拟一个调用栈只是更绕。栈解法把所有信息都保存在运行时状态中代码更短、更不容易出错。4. 代码实现一版能直接跑的Java解法附Python对照4.1 Java实现与逐行解析public int[] exclusiveTime(int n, ListString logs) { int[] res new int[n]; DequeInteger stack new ArrayDeque(); int prev 0; for (String log : logs) { String[] parts log.split(:); int id Integer.parseInt(parts[0]); String type parts[1]; int ts Integer.parseInt(parts[2]); if (start.equals(type)) { if (!stack.isEmpty()) { res[stack.peek()] ts - prev; } stack.push(id); prev ts; } else { // 题目保证合法栈顶一定是当前结束的函数 int endedId stack.pop(); res[endedId] ts - prev 1; prev ts 1; } } return res; }逐行说明res数组保存每个函数的独占时间初始全为0。DequeInteger stack用双端队列当栈用这里用ArrayDeque比Stack性能更好也符合现代Java实践。prev表示“上一次事件发生的时间点”它是整个算法的灵魂。遇到start时先给栈顶函数结算一段“从prev到现在”的时间再把新函数压栈。注意这里是peek不是pop因为栈顶函数还没结束只是被新函数打断了。遇到end时栈顶函数必然是要结束的函数给它结算ts - prev 1然后弹出。prev更新为ts 1因为ts这一格已经被结束函数占用了。4.2 Python实现对照如果你平时用Python写算法题下面这个版本可以直接背def exclusiveTime(n: int, logs: List[str]) - List[int]: res [0] * n stack [] prev 0 for log in logs: parts log.split(:) fid int(parts[0]) typ parts[1] ts int(parts[2]) if typ start: if stack: res[stack[-1]] ts - prev stack.append(fid) prev ts else: fid stack.pop() res[fid] ts - prev 1 prev ts 1 return resPython的list自带append和pop天然就是栈。注意log.split(:)返回的是字符串列表int()转换别漏。4.3 复杂度与内存分析时间复杂度O(m)其中m是日志条数。每条日志只处理一次入栈出栈都是O(1)整体线性。空间复杂度O(n)栈中最坏情况下会同时存在n个函数比如函数0调用函数1函数1再调用函数2一直到函数n-1res数组也是O(n)。这个复杂度已经是理论下界了因为你必须至少扫描一遍所有日志才有办法统计时间不可能做到O(log n)之类的对数复杂度。5. 最容易踩坑的4个细节从提交记录里捞出的真实经验5.1 end事件为什么必须“1”这是这道题最大的坑没有之一。很多人写完代码信心满满地提交结果发现示例都没过。原因在于start事件累加时用的是ts - prev但end事件累加用的是ts - prev 1。为什么不是对称的因为两个事件的时间戳语义不同。start:2意味着从时刻2开始时刻2本身不算执行时间end:5意味着在时刻5结束时刻5本身算执行时间。等价于说函数从时间2开始执行了时间2、3、4、5共4个单位。如果按照ts - prev只能算到3个单位把5漏掉了。一个辅助记忆技巧遇到end时时间戳对应的那一格是“最后执行的一格”必须计入遇到start时那个时刻属于“上一段区间的终点”不属于新函数。工程上你也可以理解成end是“左闭右闭区间的右端点”start是“左闭右开区间的左端点”。5.2 prev变量比当前时间戳更关键代码里有个很容易被忽略的细节prev并不是简单等于“上一条日志时间戳”而是“上一个事件处理完之后时间的下边界”。在start事件里prev ts在end事件里prev ts 1。这个1极其重要。假设有一段日志0:start:0 0:end:1 1:start:2 1:end:3如果end之后把prev错误地设为ts那么处理1:start:2时会发现ts - prev 0看似没问题但再往下处理1:end:3时3 - 2 1 2函数1被算成2个单位实际上它只执行了1个单位。所以prev必须代表“下一个可分配时间片的起点”而不是简单的时间戳。5.3 递归调用和同id重复入栈递归调用时同一个函数ID会在栈里出现多次。比如0:start:0 0:start:1 0:end:2 0:end:3这条日志对应函数0的两次递归调用第一次调用从0开始在1时调用了自己第二次从1执行到2结束然后第一次调用从2继续到3结束。用栈处理时栈里会出现两个0这是完全正常的。遇到end:2时弹出的应该是栈顶那个0遇到end:3时弹的是下面那个0。二者累加的时间分别是2-112和3-212共4个单位正好是总时间。有些同学遇到重复ID就害怕觉得哈希表会覆盖其实栈天然支持重复元素不需要做任何特殊处理。5.4 日志合法性的边界处理LeetCode的原题保证日志合法但真实面试和工程项目里这个假设不一定成立。常见的边界情况空日志直接返回全0数组代码自然支持因为循环体不会执行。日志不合法比如出现了0:end:5但没有对应的start此时stack.pop()会抛出异常。如果要做防御性编程可以在end时检查栈是否为空或者判断栈顶是否等于当前id。同一个时间戳多个事件理论上是允许的。比如0:end:5和1:start:5放一起只要日志顺序正确就没问题。由于end会把prev设为ts1后面start的ts-prev可能是负数——不过在合法序列里不会出现这种情况因为不可能在函数0结束的同一时刻开启一个本应在它之前执行的函数。函数ID不在0到n-1之间原题不会出现但真实数据里日志可能来自未埋点的第三方库建议过滤。6. 从题目到工程用同样的思路实现真实调用耗时分析6.1 实战变体日志不保证有序怎么办真实系统的日志往往是多线程并发写的落盘顺序可能和实际发生顺序不一致。如果日志没排序直接套上面的解法会得到错误结果因为start和end的顺序被打乱了。简单的处理方案是先按时间戳排序。但要小心同一时间戳下start和end的相对顺序会影响嵌套关系。一个比较稳的做法是按(时间戳, 事件类型优先级)排序约定同一时刻end排在start前面或者反过来并在日志ID里加上全局自增序号来保证同时间戳事件的原始顺序。更稳妥的方案是改造埋点层给每条日志打上进程内单调递增的序列号按“时间戳序列号”双字段排序这样能还原出真实的调用顺序。6.2 实战变体多线程下多组调用栈真实分布式系统日志里通常带线程ID不同线程的调用栈是互相独立的。你不能把所有线程的日志混进同一个栈里算否则一个线程的函数A还没结束另一个线程的函数B就把栈顶抢了。解法是维护一个Map线程ID, Deque函数ID每个线程一个栈每个线程还要维护一个独立的prev。为了减少内存占用可以只维护“活跃线程”的栈线程结束后清理掉。基本逻辑和单栈解法一模一样只是多了一层按线程分组。6.3 从独占时间到Span自耗时统计如果你接触过分布式链路追踪系统比如Jaeger、SkyWalking、Zipkin会发现“Span的self_time”和“函数独占时间”本质上是同一个概念。一个Span代表一次调用它可能有多个子Span它的self_time等于Span总耗时 - 所有子Span耗时之和。在实现里你可以用一棵调用树来表达整个调用链每个节点记录自己的开始时间、结束时间、子节点列表。后序遍历这棵树就能算出每个节点的self_time。这比用栈更直观但代价是内存占用更高因为你要先构建完整调用树才能统计。栈解法的优势是单次扫描即出结果适合日志规模特别大的场景。我后来在组里做过一个内部工具就是把这道题的思路封装成纯流式处理器日志逐行读入遇到start就临时挂起父函数遇到end就结算当前函数。线上几百万条日志跑下来内存占用稳定在几十MB以内比先构建全量调用树再统计的方案轻量得多。最后再分享一个小技巧面试时如果你的解法里用到了prev ts 1面试官基本能一眼看出你真正理解了这道题。你可以主动解释end时间戳包含在该函数耗时内所以下一个事件要从ts1开始计时。这一句话通常比闷头写代码加分更多。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
