函数的独占时间

记住这套口诀:start 先给栈顶补上「被打断前」的时间,end 给栈顶补上「闭区间(+1)」的时间。下面每一帧都在套它。

开场:运行栈是空的,prev=0(下一段计时从时刻 0 开始)。下方流里每条日志写成「函数·起/止·时刻」,我们从左往右逐条处理。

我们随身带三样东西:① 运行栈(栈顶 = 此刻真正在 CPU 上跑的函数);② prev(下一段计时该从哪个时刻起算);③ 答案数组(每个函数累计的独占片数)。三者随每条日志联动更新。

读第 0 条:函数 0 在时刻 0 开始。先看栈里有没有正在跑的函数(它要被打断)。

栈是空的,没有函数被打断,无需结算。 再把函数 0 压栈成为新栈顶,prev 跳到 0(下一段从这里起算)。

读第 1 条:函数 1 在时刻 2 开始。先看栈里有没有正在跑的函数(它要被打断)。

栈顶函数 0 被打断:把 prev=0 到 2 这段 2 - 0 = 2 片先记到 f0。 再把函数 1 压栈成为新栈顶,prev 跳到 2(下一段从这里起算)。

读第 2 条:函数 1 在时刻 3 结束。它一定是当前栈顶,准备结算它的闭区间。

结算闭区间:3 - 2 + 1 = 2 片记到 f1(end 含当前时刻所以 +1)。弹出 f1,prev 跳到 3 + 1 = 4。

读第 3 条:函数 0 在时刻 4 结束。它一定是当前栈顶,准备结算它的闭区间。

结算闭区间:4 - 4 + 1 = 1 片记到 f0(end 含当前时刻所以 +1)。弹出 f0,prev 跳到 4 + 1 = 5。

读第 4 条:函数 2 在时刻 5 开始。先看栈里有没有正在跑的函数(它要被打断)。

栈是空的,没有函数被打断,无需结算。 再把函数 2 压栈成为新栈顶,prev 跳到 5(下一段从这里起算)。

读第 5 条:函数 2 在时刻 7 开始。先看栈里有没有正在跑的函数(它要被打断)。

栈顶函数 2 被打断:把 prev=5 到 7 这段 7 - 5 = 2 片先记到 f2。 再把函数 2 压栈成为新栈顶,prev 跳到 7(下一段从这里起算)。

读第 6 条:函数 2 在时刻 9 结束。它一定是当前栈顶,准备结算它的闭区间。

结算闭区间:9 - 7 + 1 = 3 片记到 f2(end 含当前时刻所以 +1)。弹出 f2,prev 跳到 9 + 1 = 10。

读第 7 条:函数 2 在时刻 10 结束。它一定是当前栈顶,准备结算它的闭区间。

结算闭区间:10 - 10 + 1 = 1 片记到 f2(end 含当前时刻所以 +1)。弹出 f2,prev 跳到 10 + 1 = 11。

逐个核对:f0 在被 1 打断前跑 0~1(2 片),回来后跑 4(1 片),共 3;f1 跑 2~3 闭区间共 2;f2 自递归两层 5~9 与 10,共 6。每片都没漏、没重复。

所有日志处理完,栈清空。最终答案 [3, 2, 6]。栈 + prev 游标这套模拟,一遍线性扫描就把嵌套与递归的独占时间全部分清。

先想清:瞬时为 1、自递归全归本函数、顺序调用各算各的。

两个高频追问,核心是「后进先出的嵌套」与「自递归累加到同一 id」。