LeetCode 题解工作台
有向图中最大颜色值
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。 给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [a j , b j…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 动态·规划
答案摘要
求出每个点的入度，进行拓扑排序。 定义一个二维数组 ，其中 表示从起点到 点，颜色为 的节点数目。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 动态·规划 题型思路
题目描述
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。
给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条 有向边 。
图中一条有效 路径 是一个点序列 x1 -> x2 -> x3 -> ... -> xk ，对于所有 1 <= i < k ，从 xi 到 xi+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。
示例 1：
输入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]] 输出：3 解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 "a" 的节点（上图中的红色节点）。
示例 2：
输入：colors = "a", edges = [[0,0]] 输出：-1 解释：从 0 到 0 有一个环。
提示：
n == colors.lengthm == edges.length1 <= n <= 1050 <= m <= 105colors只含有小写英文字母。0 <= aj, bj < n
解题思路
方法一：拓扑排序 + 动态规划
求出每个点的入度，进行拓扑排序。
定义一个二维数组 ，其中 表示从起点到 点，颜色为 的节点数目。
从 点出发，遍历所有出边 ，更新 ，其中 是 点的颜色。
答案为数组 中的最大值。
如果图中有环，则无法遍历完所有点，返回 。
时间复杂度 ，空间复杂度 。其中 是字母表大小，这里为 ，而且 和 分别是节点数和边数。
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
indeg = [0] * n
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
indeg[b] += 1
q = deque()
dp = [[0] * 26 for _ in range(n)]
for i, v in enumerate(indeg):
if v == 0:
q.append(i)
c = ord(colors[i]) - ord('a')
dp[i][c] += 1
cnt = 0
ans = 1
while q:
i = q.popleft()
cnt += 1
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
c = ord(colors[j]) - ord('a')
for k in range(26):
dp[j][k] = max(dp[j][k], dp[i][k] + (c == k))
ans = max(ans, dp[j][k])
return -1 if cnt < n else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m + 26*(n + m)) accounting for topological sort and color count propagation for 26 letters. Space complexity is O(26*n) for the DP table tracking color counts per node. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if you can detect cycles before processing paths to avoid invalid results.
- question_mark
Use topological sort to guarantee that color counts propagate correctly without revisiting nodes.
- question_mark
Verify the maximum color frequency along each path, not just cumulative edge counts.
常见陷阱
外企场景- error
Failing to detect cycles leading to incorrect color value calculation.
- error
Updating color counts incorrectly when multiple predecessors share different color distributions.
- error
Assuming only a single color propagates along a path rather than tracking all 26 letters.
进阶变体
外企场景- arrow_right_alt
Compute the smallest color value along a path instead of the largest.
- arrow_right_alt
Handle graphs where nodes can have multiple colors assigned and count maximum frequency.
- arrow_right_alt
Find the number of distinct paths that achieve the largest color value.