Meta 函数Exclusive Time：嵌套栈与End含端点

题目重点：解析单线程函数开始结束日志，扣除子调用时间，处理包含结束时刻的离散计时。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练id:start/end:timestamp，单线程正常嵌套，整数tick，start与end均含端点；可以递归相同id，空日志返回n个0。
同题只有标准标签未给壳内时钟细则，本文离散tick合同需确认；连续时间或end不含端点时+1不同。

解题路线

stack保存当前调用链，cursor为尚未归属的第一tick。start事件t先给当前栈顶加t−cursor，再push新id，cursor=t。
end事件t必须匹配stack顶，给结束函数加t+1−cursor，pop后cursor=t+1。结束包含t，因此下一个可执行tick才t+1。
只给栈顶计时，父在child占用期间不累计；child返回后父从cursor继续。相同id递归两层仍按真实执行tick加到相同总量，不重复父层间隔。
检查id范围/时间顺序/缺start或未closed；顶层调用之间gap不归任何函数。不能把所有time相邻差无条件分给某id。
独立验证可对每tick找覆盖该tick最深调用并计数，这与实现的cursor/stack归账不同，能发现end少1错误。

手动走一遍

0:start:0,1:start:2,1:end:5,0:end:6，函数0占0/1/6共3，函数1占2..5共4；单start0/end0应1不是0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def exclusive_times(n,logs):
    """id:start/end:timestamp, single-thread nested execution, integer ticks.
    start inclusive, end inclusive; empty logs ->zeros; chronological and matched.
    """
    if n<0:raise ValueError('nonnegative function count')
    totals=[0]*n;stack=[];cursor=0;last=None
    for log in logs:
        parts=log.split(':')
        if len(parts)!=3:raise ValueError('three log fields')
        identity,kind,time=parts;identity=int(identity);time=int(time)
        if not 0<=identity<n or time<0 or last is not None and time<last:raise ValueError('id/time')
        last=time
        if kind=='start':
            if time<cursor:raise ValueError('overlapping tick')
            if stack:totals[stack[-1]]+=time-cursor
            stack.append(identity);cursor=time
        elif kind=='end':
            if not stack or stack[-1]!=identity or time+1<cursor:raise ValueError('unmatched end')
            totals[stack.pop()]+=time+1-cursor;cursor=time+1
        else:raise ValueError('unknown event')
    if stack:raise ValueError('unclosed call')
    return totals

复杂度

O(L)日志时间、O(depth)调用栈、O(n)结果，时间跨度很大仍不逐tick模拟。日志字符串解析成本按总字符数，不能只按L假定无限长时间戳常数。

易错点与追问

容易失分的边界

end少+1漏每次结束tick。
按函数整段end−start计会把子时间重复加父。

继续深挖

多线程日志必须每thread独立stack/cursor，最终function totals怎样合并？
日志乱序或缺失不可总是重构唯一调用，应报告不足证据而非猜结束。