LeetCode 面试题 08.10. 颜色填充

2026-03-28 HGNULB 约 10 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 面试题 08.10. 颜色填充

题意分析

给定二维像素矩阵 image、起点坐标 (sr, sc) 和新颜色 newColor，要求模拟画图软件的「油漆桶」：把与起点上下左右连通且颜色与起点相同的那一整块像素全部改成新颜色，返回修改后的矩阵。

「连通」的定义只允许四个方向，不含对角线——这一条必须先确认，因为八连通会把两块只在角上相碰的区域误判成同一块。

约束里透露的信号有三个。第一，「相同颜色 + 四向连通」本质是在网格上找一个连通块，而网格就是一张隐式的图，每个格子是点、相邻同色格子之间是边，所以这是一次从单点出发的整图遍历。第二，起点颜色 image[sr][sc] 必须在任何修改发生之前取出来存好，一旦第一格被改写，后续判断的参照就没了。第三，题目要求原地返回同一个矩阵，说明可以直接把「已改成新色」当作访问标记，不必额外开 visited 数组。

边界有两处容易被忽略。一是新旧颜色相同：此时染色不改变任何东西，但如果仍以「颜色等于旧色就继续递归」为条件，格子被改成新色后颜色没变化，标记失效，两个相邻格子会互相无限递归下去，直接栈溢出。二是矩阵只有一个格子，或起点所在的连通块就是它自己，此时只改一格即返回；越界判断必须写在读取 image[i][j] 之前，否则一进入就下标异常。

解法：深度优先搜索

核心思路

暴力想法是反复扫描整个矩阵：每一轮把「与已染色格子相邻且颜色为旧色」的格子染掉，直到某一轮没有任何变化。这样能得到正确结果，但瓶颈明显——连通块是一条细长的蛇形时，每轮只能推进一格，需要 $O(mn)$ 轮，每轮又要 $O(mn)$ 次扫描，总代价退化到 $O(m^2n^2)$。

观察到「推进」这个动作其实不需要重新扫描：一个格子刚被染色时，唯一可能新变得可染的就是它的四个邻居。顺着这条线索，从起点出发沿邻居关系一路走下去就够了，每个格子只需被访问一次。

于是维护的核心状态就是矩阵本身。显式写出不变量：任何时刻，矩阵里颜色为 newColor 且从起点四向连通的格子，都是已经处理完毕（自身已染色、且四个邻居都已被尝试过或正在栈上等待）的格子；颜色仍为 oc 的格子则一定还没被访问。这条不变量让「颜色本身」承担了访问标记的职责，省掉一个 visited 数组。

单次递归的语义随之固定为：dfs(i, j) 负责「如果 (i, j) 合法且属于待染集合，就把它连同它所在的剩余连通部分全部染成新色」。四个剪枝条件——越界、颜色不等于 oc、颜色已等于 nc——共同保证不变量在递归前后都成立。

最后一个条件 image[i][j] == nc 正是为「新旧同色」这个退化情形准备的：它让第一次调用就直接返回，把无限递归掐死在入口。

解题步骤

先取出起点原色 oc = image[sr][sc]，再做任何写入。这一步的顺序不能反，因为一旦起点被染成新色，判断「哪些格子属于同一块」的参照就丢失了。

把 image、oc、nc 提升为成员变量（Go 里用闭包捕获）。递归每层都要读它们，放在参数里传递只会让签名臃肿。

方向数组用 {-1, 0, 1, 0, -1} 这种压缩写法。相邻两项 (dirs[k], dirs[k+1]) 恰好构成上、右、下、左四个偏移，比写两个数组或四行硬编码更短，白板上不易写错。

递归入口先判越界：i < 0 || i >= m || j < 0 || j >= n。必须排在读取 image[i][j] 之前，靠短路求值保证不会越界访问。

再判颜色不匹配：image[i][j] != oc 直接返回，这把「不属于该连通块」和「已经被染成新色」两种情况一起拦下了——因为染色后颜色变成 nc，自然不再等于 oc。

最后判 image[i][j] == nc：只在 oc == nc 时才起作用，此时上一条判断失效，靠这条阻止无限递归。

先染色再递归四个邻居。染色必须在递归之前完成，它同时是「做事」和「打标记」；如果放到递归之后，同一格子会被四邻居反复推入栈，直接爆栈。

函数返回 image 本身，题目要求原地修改，不需要拷贝。

以 image = [[1,1,1],[1,1,0],[1,0,1]]、sr = 1、sc = 1、newColor = 2 走一遍。先取 oc = image[1][1] = 1，nc = 2。

进入 dfs(1, 1)：不越界，颜色为 1 等于 oc，且不等于 nc，通过。染成 2，矩阵变为 [[1,1,1],[1,2,0],[1,0,1]]。依次尝试四个邻居。

上邻 dfs(0, 1)：颜色 1，通过，染成 2。它再展开——上邻 (-1, 1) 越界返回；右邻 (0, 2) 颜色 1，染成 2，其右邻 (0, 3) 越界，下邻 (1, 2) 颜色 0 不等于 oc 返回，左邻回到 (0, 1) 时颜色已是 2 不等于 oc 返回；下邻 (1, 1) 已是 2，返回；左邻 (0, 0) 颜色 1，染成 2，其下邻 (1, 0) 颜色 1，染成 2，(1, 0) 的下邻 (2, 0) 颜色 1 染成 2，(2, 0) 的下邻 (3, 0) 越界、右邻 (2, 1) 颜色 0 返回。

回到 dfs(1, 1) 的其余三个方向：右邻 (1, 2) 颜色 0 返回；下邻 (2, 1) 颜色 0 返回；左邻 (1, 0) 已是 2 返回。

最终矩阵为 [[2,2,2],[2,2,0],[2,0,1]]。注意右下角的 1 虽然颜色与起点相同，但它被两个 0 隔开，不与起点四向连通，因此保持不变——这正是「连通」而非「同色」的区别。

再看退化用例 image = [[0,0,0],[0,1,1]]、sr = 1、sc = 1、newColor = 1：oc = 1 恰好等于 nc。进入 dfs(1, 1) 后前两个条件都通过，第三个条件 image[1][1] == nc 成立，立即返回，矩阵原样输出。若少了这一条，(1,1) 染色后颜色仍是 1，它会去访问 (1,2)，(1,2) 又会回访 (1,1)，两格互相调用直至栈溢出。

代码实现

class Solution {
    private int[] dirs = {-1, 0, 1, 0, -1};
    private int[][] image;
    private int nc;
    private int oc;

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        nc = newColor;
        // 必须在任何写入之前取出起点原色。
        oc = image[sr][sc];
        this.image = image;
        dfs(sr, sc);
        return image;
    }

    private void dfs(int i, int j) {
        // image[i][j] == nc 专门用于新旧同色时阻断无限递归。
        if (i < 0 || i >= image.length || j < 0 || j >= image[0].length || image[i][j] != oc
            || image[i][j] == nc) {
            return;
        }
        image[i][j] = nc;
        for (int k = 0; k < 4; ++k) {
            dfs(i + dirs[k], j + dirs[k + 1]);
        }
    }
}

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
    // 必须在任何写入之前取出起点原色。
    oc := image[sr][sc]
    m, n := len(image), len(image[0])
    dirs := []int{-1, 0, 1, 0, -1}
    var dfs func(i, j int)
    dfs = func(i, j int) {
        // image[i][j] == newColor 专门用于新旧同色时阻断无限递归。
        if i < 0 || i >= m || j < 0 || j >= n || image[i][j] != oc || image[i][j] == newColor {
            return
        }
        image[i][j] = newColor
        for k := 0; k < 4; k++ {
            dfs(i+dirs[k], j+dirs[k+1])
        }
    }
    dfs(sr, sc)
    return image
}

复杂度分析

时间复杂度：$O(mn)$，m、n 为矩阵行列数。每个格子最多被染色一次，染色后颜色不再等于 oc，后续访问在入口即被拦下；每个格子发起 4 次邻居调用，总调用次数不超过 $4mn$，均摊到每格是常数。

空间复杂度：$O(mn)$，来自递归栈。最坏情况是整个矩阵同色且排布成蛇形路径，递归深度可达 $mn$；由于颜色本身充当访问标记，没有额外的 visited 数组开销。

关键点总结

用「结果本身」当访问标记是网格染色题的通用省空间技巧：一旦目标状态与初始状态可区分，就不需要额外的 visited；一旦不可区分（本题的新旧同色），就必须补一条专门的判断兜底。

越界判断永远排在数组读取之前，依赖短路求值。这条在任何语言的网格 DFS 里都成立，是面试官会盯的细节。

标记要在递归之前打，即「先染色，再扩散」。放到递归之后是网格搜索最典型的爆栈原因。

方向数组 {-1, 0, 1, 0, -1} 的压缩写法值得记住，四向搜索题都能复用，比四行硬编码更快也更不易漏方向。

面试视角：这题本身简单，区分度在追问上。被问到「$m, n$ 到 $10^3$ 量级会不会爆栈」时，应主动给出改写成 BFS 显式队列的方案——时间同为 $O(mn)$，空间换成队列且不占用调用栈；被问到「怎么统计染了多少格」时，指出在染色处累加计数即可，这就是 695 题。

先想清楚退化情形再动手：本题的 oc == nc 是典型的「看起来无害、实际会死循环」的输入，能在写代码前主动提出来，比写完被 hack 出来印象好得多。

易错点总结

忘记 image[i][j] == nc 这条判断：image = [[0,0],[0,0]]、起点 (0,0)、newColor = 0 时，四个格子互相递归，栈溢出崩溃。

先染色再取 oc：写成 image[sr][sc] = newColor; oc = image[sr][sc];，oc 变成了新色，[[1,1],[1,1]] 染成 2 时只有起点被改，输出 [[2,1],[1,1]]。

越界判断写在颜色判断之后：条件顺序写成 image[i][j] != oc || i < 0 || ...，image = [[1]] 时递归到 (-1, 0) 立刻数组下标越界异常。

染色放在递归之后：先递归四个邻居再执行 image[i][j] = nc，[[1,1]] 里两格互相调用永不返回，栈溢出。

方向数组写错一项：把 {-1, 0, 1, 0, -1} 写成 {-1, 0, 1, 0, 1}，最后一组偏移变成 (0, 1) 与第一组重复，[[1,1],[1,1]] 起点 (1,1) 时左邻和上邻漏搜，输出 [[1,2],[1,2]] 之类的残缺结果。

用八方向搜索：额外加上四个对角偏移后，image = [[1,0],[0,1]] 起点 (0,0) 会把右下角的 1 也染掉，而它与起点并不四向连通。

误以为要染所有同色格子：跳过连通性直接扫全矩阵替换，[[1,0,1]] 起点 (0,0) 会把末尾那个被 0 隔开的 1 也改掉。

image[0].length 在空矩阵上取用：题目虽保证非空，但若把越界判断写成先读 image[i].length（用行内长度而非首行长度），在锯齿数组场景会取到错误上界；网格题统一用 image[0].length 更安全。

Go 里把 image 作为值参数后又重新 make 一个切片：image = make([][]int, m) 会切断与调用方的共享底层数组，返回的是新矩阵而原矩阵未变，本题恰好因为返回了新变量而看不出问题，但在「无返回值原地修改」的变体里会直接错。

在 Java 里把 dirs 写成局部变量却在递归函数外声明：若忘记 this.image = image 这类赋值，成员变量仍为 null，第一次递归就空指针异常。

相似题目

题目	难度	考察点
733. 图像渲染	简单	与本题完全同题，可直接套用同一份 `dfs`
200. 岛屿数量	中等	需要在外层遍历所有起点，每次完整染色计一个连通块
695. 岛屿的最大面积	中等	递归带返回值累加格子数，再对所有连通块取最大
130. 被围绕的区域	中等	反向染色：从边界的 `O` 出发标记安全区，剩余 `O` 才需要翻转
1020. 飞地的数量	中等	同样从边界反向消除，最后统计残留陆地数而非区域数
面试题 16.19. 水域大小	中等	改为八连通，且要收集所有连通块大小后排序输出
994. 腐烂的橘子	中等	求扩散所需轮数，必须用多源 BFS 分层，DFS 无法保证最短时间
542. 01 矩阵	中等	求每格到最近 `0` 的距离，同样是多源 BFS，答案是距离场而非染色结果
934. 最短的桥	中等	先用 DFS 圈出第一座岛，再用 BFS 从整座岛出发扩散求最短连接距离
79. 单词搜索	中等	路径搜索而非连通块，标记必须在回溯时撤销，与本题的永久标记正好相反
329. 矩阵中的最长递增路径	困难	邻接条件从「同色」变成「递增」，形成 DAG，需要记忆化而非单纯标记