通知所有员工所需的时间 图解题解
这道题到底在问什么
- 输入
- n=8, head=0, manager=[−1,0,0,1,1,2,2,3], informTime=[1,2,3,4,0,0,0,0]
- 输出
- 7(路径 0→1→3→7:1+2+4)
最优解：一步一步想明白
- 3记住「建邻接表 → DFS 累加 informTime → 取最大的那条链」,下面逐帧套它。
- 4先看这棵管理树:负责人是员工 0(橙色)。右侧这张表列出每个员工通知下属要花的分钟数 informTime:0 要 1 分钟、1 要 2 分钟、2 要 3 分钟、3 要 4 分钟,4 到 7 都是叶子、为 0。
- 5反向建邻接表:扫一遍 manager,把每个人挂到上级的下属列表里。于是 0 的下属是 1、2;1 的下属是 3、4;2 的下属是 5、6;3 的下属是 7。下面从 0 开始 DFS。
- 6初始化:把负责人 0 连同它的开始时刻 t = 0 压进栈(蓝色)。负责人自己在第 0 分钟就「收到」通知,所以 t = 0。接下来反复弹栈顶处理,直到栈空。
- 7弹出栈顶:员工 0,它开始收到通知的时刻 t = 0(蓝牌)。没超过当前 ans=0,答案不变。
- 8员工 0 通知下属要 1 分钟,所以它的下属 1、2 的开始时刻都是 0 + 1 = 1,压进栈等着处理。员工 0 自己处理完、变绿。
- 9继续弹栈顶:员工 2,它开始收到通知的时刻 t = 1(蓝牌)。比之前的 ans 大,把答案刷新成 1。
- 10员工 2 通知下属要 3 分钟,所以它的下属 5、6 的开始时刻都是 1 + 3 = 4,压进栈等着处理。员工 2 自己处理完、变绿。
- 11再弹栈顶:员工 6,它开始收到通知的时刻 t = 4(蓝牌)。比之前的 ans 大,把答案刷新成 4。
- 12员工 6 是叶子、没有下属,不用再往下传。它处理完、变绿。
- 13接着弹:员工 5,它开始收到通知的时刻 t = 4(蓝牌)。没超过当前 ans=4,答案不变。
- 14员工 5 是叶子、没有下属,不用再往下传。它处理完、变绿。
- 15接着弹:员工 1,它开始收到通知的时刻 t = 1(蓝牌)。没超过当前 ans=4,答案不变。
- 16员工 1 通知下属要 2 分钟,所以它的下属 3、4 的开始时刻都是 1 + 2 = 3,压进栈等着处理。员工 1 自己处理完、变绿。
- 17接着弹:员工 4,它开始收到通知的时刻 t = 3(蓝牌)。没超过当前 ans=4,答案不变。
- 18员工 4 是叶子、没有下属,不用再往下传。它处理完、变绿。
- 19接着弹:员工 3,它开始收到通知的时刻 t = 3(蓝牌)。没超过当前 ans=4,答案不变。
- 20员工 3 通知下属要 4 分钟,所以它的下属 7 的开始时刻都是 3 + 4 = 7,压进栈等着处理。员工 3 自己处理完、变绿。
- 21接着弹:员工 7,它开始收到通知的时刻 t = 7(蓝牌)。比之前的 ans 大,把答案刷新成 7。
- 22员工 7 是叶子、没有下属,不用再往下传。它处理完、变绿。
- 23全部员工处理完。最大的累计时刻出现在员工 7 身上,它走的链是 0→1→3→7、累计 1+2+4 = 7。所以让所有人都收到通知要 7 分钟,这正是最慢那条链的耗时。
⚠️ 容易写错的地方
✗ 错：把各分支的时间相加
✓ 对：取最大的那条链,不是求和
同一个经理通知它的多个下属是并行计时的,总时间由最慢的分支决定,不能把分支时间加起来
✗ 错：以为最深的员工时间最长
✓ 对：比的是累计 informTime,不是层数
某些上级 informTime 为 0,深的链未必慢;要看 informTime 之和最大的那条
✗ 错：忘了 informTime 累加
✓ 对：下属的 t = 父的 t + 父的 informTime
员工开始收到通知的时刻是它所有上级 informTime 的累加,漏加就少算了上层耗时
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 ansC++
#include <vector>
using namespace std;
class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
vector<vector<int>> children(n);
for (int i = 0; i < n; ++i) if (manager[i] != -1) children[manager[i]].push_back(i);
int ans = 0;
vector<pair<int,int>> st{{headID, 0}};
while (!st.empty()) {
auto [u, t] = st.back(); st.pop_back();
ans = max(ans, t);
for (int v : children[u]) st.push_back({v, t + informTime[u]});
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
List<Integer>[] children = new ArrayList[n];
for (int i = 0; i < n; i++) children[i] = new ArrayList<>();
for (int i = 0; i < n; i++) if (manager[i] != -1) children[manager[i]].add(i);
int ans = 0;
Deque<int[]> st = new ArrayDeque<>();
st.push(new int[]{headID, 0});
while (!st.isEmpty()) {
int[] cur = st.pop();
ans = Math.max(ans, cur[1]);
for (int v : children[cur[0]]) st.push(new int[]{v, cur[1] + informTime[cur[0]]});
}
return ans;
}
}复杂度
时间
O(n)
建邻接表扫一遍 O(n);DFS 里每个员工恰好入栈、出栈一次,所有下属边合计也是 n−1 条,合起来 O(n)
空间
O(n)
邻接表存全部 n−1 条上下级关系是 O(n);迭代栈在宽分支/星形等情况下最坏也可到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 通知所有员工所需的时间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么先把 manager 转成邻接表(children),不直接用 manager 数组?+
manager 给的是「向上」的指针(每人指向上级),而通知是「向下」传播的,需要从一个经理快速找到它的全部下属。建一次邻接表 children 就能 O(1) 拿到任意经理的下属列表,DFS 自顶向下才走得动;直接用 manager 反查下属每次都要扫整个数组,会退化成 O(n²)。
用 DFS 还是 BFS 都行吗?+
都行。本质是求根到每个节点的累计 informTime 的最大值,DFS、BFS 都能在 O(n) 内遍历整棵树、沿途累加。也可以写成自底向上的递归 dfs(u) = informTime[u] + max(子树的 dfs),返回根的值,效果一样。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 通知所有员工所需的时间 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。