[LeetCode] 每日一题 1857. 有向图中最大颜色值（记忆化搜索）

题目描述

给你一个 有向图 ，它含有 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 。

题目链接

https://leetcode.cn/problems/largest-color-value-in-a-directed-graph

示例输入

示例 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.length

• m == edges.length

• 1 <= n <= 10^5

• 0 <= m <= 10^5

• colors 只含有小写英文字母。

• 0 <= aj, bj < n

解题思路

这题属于典型的“图上的动态规划”问题，不过我比较熟悉的是 DFS + 记忆化搜索 模板思路。题目让我们在一个有向图中寻找一条路径，使得某种颜色出现次数最多，并返回这个最大次数。

这类题目常见套路：DFS 记忆化 + 处理图中环的陷阱。
我第一眼看到这题就下意识准备掏出 DFS + 记忆化搜索的模板，但由于图中可能存在环，所以我们需要特别判断是否成环，否则会导致死递归。

关键点：区分访问状态，避免环导致的错误返回！
这里不仅要判断节点是否访问过（visited），还要判断是否正在当前路径中访问（visiting）。因此我使用 memory[index] == null 判断是否未访问，而 memory[index] = new int[]{} 表示该点“正在访问中”，如果 DFS 时再次遇到该点，就说明出现了环，直接返回空数组作为标记。

思路流程：

1. 建图，判断自环（[a,a]）可直接返回 -1

2. 定义一个 memory 二维数组记录每个节点为起点的颜色统计结果

3. 用 DFS 搜索每个节点能达到的最大颜色值，并利用 res[colors[i]-'a']++ 统计颜色

4. 若 DFS 过程中返回空数组，则代表出现环，立即返回 -1

5. 最终返回所有路径中颜色出现最多的值

代码实现

class Solution {
    public int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        int ans = 0;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            if (edge[0] == edge[1]) {
                return -1;
            }
            g.get(edge[0]).add(edge[1]);
        }
        char[] colorsArr = colors.toCharArray();
        int[][] memory = new int[n][];
        for (int i = 0; i < n; i++) {
            int[] res = dfs(i, g, colorsArr, memory);
            if (res.length == 0) {
                return -1;
            }
            ans = Math.max(ans, res[colorsArr[i] - 'a']);
        }
        return ans;
    }

    private int[] dfs(int index, List<List<Integer>> g, char[] colorsArr, int[][] memory) {
        if (memory[index] != null) {
            return memory[index];
        }
        memory[index] = new int[] {};
        int[] res = new int[26];
        List<Integer> path = g.get(index);
        for (Integer i : path) {
            int[] temp = dfs(i, g, colorsArr, memory);
            if (temp.length == 0) {
                return temp;
            }
            for (int j = 0; j < 26; j++) {
                res[j] = Math.max(res[j], temp[j]);
            }
        }
        res[colorsArr[index] - 'a']++;
        memory[index] = res;
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n + m × 26)

  • 每个节点最多访问一次，每条边最多遍历一次

  • 每次递归中涉及 26 个字母统计数组的合并与拷贝

• 空间复杂度：O(n × 26 + n + m)

  • memory 数组存储每个节点的颜色分布

  • 邻接表存图需要 O(n + m) 空间

  • 递归栈深度最坏为 n

总结

这题最大的陷阱是如何安全地判断图中是否有环。
我在实现中通过将 memory[index] 设置为空数组来标记“正在访问中”的状态，有效避免了因 DFS 反复回溯导致的死循环，也很好地兼容了记忆化搜索逻辑。整体实现思路偏模板化，但在细节处理上必须非常严谨👍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。