题目描述
思路解析动画文字版
记住「建邻接表 → DFS 累加 informTime → 取最大的那条链」,下面逐帧套它。
先看这棵管理树:负责人是员工 0(橙色)。右侧这张表列出每个员工通知下属要花的分钟数 informTime:0 要 1 分钟、1 要 2 分钟、2 要 3 分钟、3 要 4 分钟,4 到 7 都是叶子、为 0。
反向建邻接表:扫一遍 manager,把每个人挂到上级的下属列表里。于是 0 的下属是 1、2;1 的下属是 3、4;2 的下属是 5、6;3 的下属是 7。下面从 0 开始 DFS。
初始化:把负责人 0 连同它的开始时刻 t = 0 压进栈(蓝色)。负责人自己在第 0 分钟就「收到」通知,所以 t = 0。接下来反复弹栈顶处理,直到栈空。
弹出栈顶:员工 0,它开始收到通知的时刻 t = 0(蓝牌)。没超过当前 ans=0,答案不变。
员工 0 通知下属要 1 分钟,所以它的下属 1、2 的开始时刻都是 0 + 1 = 1,压进栈等着处理。员工 0 自己处理完、变绿。
继续弹栈顶:员工 2,它开始收到通知的时刻 t = 1(蓝牌)。比之前的 ans 大,把答案刷新成 1。
员工 2 通知下属要 3 分钟,所以它的下属 5、6 的开始时刻都是 1 + 3 = 4,压进栈等着处理。员工 2 自己处理完、变绿。
再弹栈顶:员工 6,它开始收到通知的时刻 t = 4(蓝牌)。比之前的 ans 大,把答案刷新成 4。
员工 6 是叶子、没有下属,不用再往下传。它处理完、变绿。
接着弹:员工 5,它开始收到通知的时刻 t = 4(蓝牌)。没超过当前 ans=4,答案不变。
员工 5 是叶子、没有下属,不用再往下传。它处理完、变绿。
接着弹:员工 1,它开始收到通知的时刻 t = 1(蓝牌)。没超过当前 ans=4,答案不变。
员工 1 通知下属要 2 分钟,所以它的下属 3、4 的开始时刻都是 1 + 2 = 3,压进栈等着处理。员工 1 自己处理完、变绿。
接着弹:员工 4,它开始收到通知的时刻 t = 3(蓝牌)。没超过当前 ans=4,答案不变。
员工 4 是叶子、没有下属,不用再往下传。它处理完、变绿。
接着弹:员工 3,它开始收到通知的时刻 t = 3(蓝牌)。没超过当前 ans=4,答案不变。
员工 3 通知下属要 4 分钟,所以它的下属 7 的开始时刻都是 3 + 4 = 7,压进栈等着处理。员工 3 自己处理完、变绿。
接着弹:员工 7,它开始收到通知的时刻 t = 7(蓝牌)。比之前的 ans 大,把答案刷新成 7。
员工 7 是叶子、没有下属,不用再往下传。它处理完、变绿。
全部员工处理完。最大的累计时刻出现在员工 7 身上,它走的链是 0→1→3→7、累计 1+2+4 = 7。所以让所有人都收到通知要 7 分钟,这正是最慢那条链的耗时。
边界:单人为 0;星形=一层的 informTime;链=沿途全加。
两个追问:邻接表为了向下找下属;DFS/BFS/自底向上递归都可。
参考代码
from typing import Listclass Solution: def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int: children = [[] for _ in range(n)] for i, p in enumerate(manager): if p != -1: children[p].append(i) ans = 0 stack = [(headID, 0)] while stack: u, t = stack.pop() ans = max(ans, t) for v in children[u]: stack.append((v, t + informTime[u])) return ans复杂度
- 时间：O(n)，建邻接表扫一遍 O(n);DFS 里每个员工恰好入栈、出栈一次,所有下属边合计也是 n−1 条,合起来 O(n)
- 空间：O(n)，邻接表存全部 n−1 条上下级关系是 O(n);迭代栈在宽分支/星形等情况下最坏也可到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么先把 manager 转成邻接表(children),不直接用 manager 数组?
追问用 DFS 还是 BFS 都行吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计二叉树中好节点的数目
LeetCode 1448 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题