函数的独占时间 图解题解
这道题到底在问什么
- 输入
- n=2, logs=["0:start:0","1:start:2","1:end:5","0:end:6"]
- 输出
- [3,4] (函数 0 被 1 打断,0 只占 0~1 和 6 共 3 片)
- 输入
- n=1, logs=["0:start:0","0:end:0"]
- 输出
- [1] (end 含当前时刻,0~0 也算 1 片)
最优解：一步一步想明白
- 3记住这套口诀:start 先给栈顶补上「被打断前」的时间,end 给栈顶补上「闭区间(+1)」的时间。下面每一帧都在套它。
- 4开场:运行栈是空的,prev=0(下一段计时从时刻 0 开始)。下方流里每条日志写成「函数·起/止·时刻」,我们从左往右逐条处理。
- 5我们随身带三样东西:① 运行栈(栈顶 = 此刻真正在 CPU 上跑的函数);② prev(下一段计时该从哪个时刻起算);③ 答案数组(每个函数累计的独占片数)。三者随每条日志联动更新。
- 6读第 0 条:函数 0 在时刻 0 开始。先看栈里有没有正在跑的函数(它要被打断)。
- 7栈是空的,没有函数被打断,无需结算。 再把函数 0 压栈成为新栈顶,prev 跳到 0(下一段从这里起算)。
- 8读第 1 条:函数 1 在时刻 2 开始。先看栈里有没有正在跑的函数(它要被打断)。
- 9栈顶函数 0 被打断:把 prev=0 到 2 这段 2 - 0 = 2 片先记到 f0。 再把函数 1 压栈成为新栈顶,prev 跳到 2(下一段从这里起算)。
- 10读第 2 条:函数 1 在时刻 3 结束。它一定是当前栈顶,准备结算它的闭区间。
- 11结算闭区间:3 - 2 + 1 = 2 片记到 f1(end 含当前时刻所以 +1)。弹出 f1,prev 跳到 3 + 1 = 4。
- 12读第 3 条:函数 0 在时刻 4 结束。它一定是当前栈顶,准备结算它的闭区间。
- 13结算闭区间:4 - 4 + 1 = 1 片记到 f0(end 含当前时刻所以 +1)。弹出 f0,prev 跳到 4 + 1 = 5。
- 14读第 4 条:函数 2 在时刻 5 开始。先看栈里有没有正在跑的函数(它要被打断)。
- 15栈是空的,没有函数被打断,无需结算。 再把函数 2 压栈成为新栈顶,prev 跳到 5(下一段从这里起算)。
- 16读第 5 条:函数 2 在时刻 7 开始。先看栈里有没有正在跑的函数(它要被打断)。
- 17栈顶函数 2 被打断:把 prev=5 到 7 这段 7 - 5 = 2 片先记到 f2。 再把函数 2 压栈成为新栈顶,prev 跳到 7(下一段从这里起算)。
- 18读第 6 条:函数 2 在时刻 9 结束。它一定是当前栈顶,准备结算它的闭区间。
- 19结算闭区间:9 - 7 + 1 = 3 片记到 f2(end 含当前时刻所以 +1)。弹出 f2,prev 跳到 9 + 1 = 10。
- 20读第 7 条:函数 2 在时刻 10 结束。它一定是当前栈顶,准备结算它的闭区间。
- 21结算闭区间:10 - 10 + 1 = 1 片记到 f2(end 含当前时刻所以 +1)。弹出 f2,prev 跳到 10 + 1 = 11。
- 22逐个核对:f0 在被 1 打断前跑 0~1(2 片),回来后跑 4(1 片),共 3;f1 跑 2~3 闭区间共 2;f2 自递归两层 5~9 与 10,共 6。每片都没漏、没重复。
- 23所有日志处理完,栈清空。最终答案 [3, 2, 6]。栈 + prev 游标这套模拟,一遍线性扫描就把嵌套与递归的独占时间全部分清。
⚠️ 容易写错的地方
✗ 错：end 段忘记 +1
✓ 对：end 是闭区间,时长 = ts - prev + 1
0:start:0 与 0:end:0 应为 1 片,漏 +1 会算成 0
✗ 错：start 时没先结算栈顶
✓ 对：先把被打断那段记给栈顶,再压新函数
不先结算,被打断函数的运行时间就漏掉了
✗ 错：prev 更新错位
✓ 对：start 后 prev = ts;end 后 prev = ts + 1
end 已把该时刻算进闭区间,下一段必须从 ts+1 开始,否则重复计时
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
ans = [0] * n
stack = []
prev = 0
for log in logs:
fid, typ, ts = log.split(':')
fid, ts = int(fid), int(ts)
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
return ansC++
#include <sstream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> ans(n), st;
int prev = 0;
for (string log : logs) {
int p1 = log.find(':'), p2 = log.find(':', p1 + 1);
int id = stoi(log.substr(0, p1));
string typ = log.substr(p1 + 1, p2 - p1 - 1);
int ts = stoi(log.substr(p2 + 1));
if (typ == "start") {
if (!st.empty()) ans[st.back()] += ts - prev;
st.push_back(id);
prev = ts;
} else {
ans[st.back()] += ts - prev + 1;
st.pop_back();
prev = ts + 1;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] exclusiveTime(int n, List<String> logs) {
int[] ans = 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]);
int ts = Integer.parseInt(parts[2]);
if (parts[1].equals("start")) {
if (!st.isEmpty()) ans[st.peek()] += ts - prev;
st.push(id);
prev = ts;
} else {
ans[st.pop()] += ts - prev + 1;
prev = ts + 1;
}
}
return ans;
}
}复杂度
时间
O(L)
L 为日志条数,每条日志只读一次,拆字段加进出栈都是常数操作
空间
O(n + D)
n 为答案数组长度(函数数量),结果数组占 n;D 为最大调用栈深度,同一函数可多次递归入栈(动画里栈一度是 [2,2]),最坏 D 到 O(L)(日志条数级);不计输出则辅助空间 O(D)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 函数的独占时间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用栈而不是简单的计数器?+
因为函数可以嵌套调用与自我递归,任意时刻可能有多个函数处于「已开始未结束」状态,后开始的先结束(后进先出)。栈正好表达这种嵌套关系,栈顶始终是当前真正在 CPU 上跑的那个函数。
同一个函数自己递归调用,时间会不会算错?+
不会。每层 start 都先结算上一层(同一 id)被打断的时间,end 再结算本层闭区间,两层时间都累加到同一个 id 上,最终是该函数所有层的总和。例如 0 自递归两层 0~6 的结果就是 7。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 函数的独占时间 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。