994. 腐烂的橘子#

今天要聊的这道题，让我想起了在生鲜电商实习时的一个场景…

🍊 从生鲜仓库说起#

产品经理：“我们仓库里有一批橘子，已经发现有几个坏掉了。假设每天坏橘子会污染它周围的新鲜橘子，我们需要预估多少天后所有橘子会坏掉，这样才能及时调整库存…”

听起来是不是很像LeetCode 994题？

问题描述#

题目目标#

在给定的 m x n 网格 grid 中，每个单元格可能有以下三种值之一：0 代表空单元格，1 代表新鲜橘子，2 代表腐烂橘子。每分钟，腐烂橘子会使其四个方向上相邻的新鲜橘子腐烂。请返回直到网格中没有新鲜橘子为止所需的最小分钟数；如果无法做到，返回 -1。

示例 1#

输入： grid = [[2,1,1],[1,1,0],[0,1,1]] 输出： 4 网格示意：

2 1 1
1 1 0
0 1 1

text

说明： 图示把输入结构和输出结果并排展开后，会更容易直接看清题目的变化过程。

💡 问题的本质#

这道题是这样描述的：

在一个 N × M 的网格中，每个单元格有三种可能的值：
- 0 表示空格子
- 1 表示新鲜橘子
- 2 表示腐烂的橘子

每分钟，腐烂的橘子会让上、下、左、右四个方向的新鲜橘子腐烂。
求需要多少分钟，整个网格中的橘子都会腐烂？如果不可能全部腐烂，返回 -1。

示例：
输入：[
    [2,1,1],
    [1,1,0],
    [0,1,1]
]
输出：4

plaintext

🤔 第一反应可能是DFS？#

很多同学看到网格搜索就想到DFS（深度优先搜索）。但等等，这题有个关键词：时间！

想象一下腐烂过程：

第0分钟：初始状态，有些橘子已经腐烂
第1分钟：这些腐烂橘子同时感染周围的橘子
第2分钟：新腐烂的橘子又同时感染周围的…

这不就是**广度优先搜索(BFS)**的经典场景吗？

⚡ 代码实现：BFS的完美运用#

class Solution {
    public int orangesRotting(int[][] grid) {
        // rows：网格行数；cols：网格列数，用于遍历和边界判断
        int rows = grid.length, cols = grid[0].length;
        // queue：BFS 队列，存储“当前已经腐烂”的橘子坐标
        Queue<int[]> queue = new LinkedList<>();
        // freshCount：当前网格中新鲜橘子（值为 1）的总数量
        int freshCount = 0;

        // 第一步：遍历整个网格
        // - 遇到腐烂橘子（2）就入队，作为 BFS 的初始多源起点
        // - 遇到新鲜橘子（1）就计数，后续用于判断是否全部被感染
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    // 记录一个腐烂橘子的位置，作为当前层感染源
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    // 统计新鲜橘子数量
                    freshCount++;
                }
            }
        }

        // 边界条件：如果一开始就没有新鲜橘子，不需要等待，答案为 0 分钟
        if (freshCount == 0) return 0;

        // directions：四个方向向量（上、下、左、右）
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        // minutes：BFS 层数，也就是经过的分钟数
        int minutes = 0;

        // 开始 BFS 分层扩散：每一层代表“同一分钟内”同时发生的感染
        while (!queue.isEmpty() && freshCount > 0) {
            // 进入下一分钟
            minutes++;
            // size 记录当前层节点数：本分钟只处理这些旧腐烂橘子
            int size = queue.size();

            // 依次处理本分钟的每个腐烂橘子
            for (int i = 0; i < size; i++) {
                // 取出一个腐烂橘子的坐标
                int[] pos = queue.poll();

                // 尝试向四个方向扩散感染
                for (int[] dir : directions) {
                    // 计算相邻格子的行坐标
                    int newRow = pos[0] + dir[0];
                    // 计算相邻格子的列坐标
                    int newCol = pos[1] + dir[1];

                    // 仅当相邻位置在网格内，且该位置是新鲜橘子(1)时才会被感染
                    if (newRow >= 0 && newRow < rows && 
                        newCol >= 0 && newCol < cols && 
                        grid[newRow][newCol] == 1) {

                        // 把新鲜橘子改为腐烂，表示它在“当前分钟末”已被感染
                        grid[newRow][newCol] = 2;
                        // 新腐烂橘子加入队列，下一分钟它将继续感染周围橘子
                        queue.offer(new int[]{newRow, newCol});
                        // 新鲜橘子数量减 1
                        freshCount--;
                    }
                }
            }
        }

        // BFS 结束后：
        // - freshCount == 0：全部感染完成，返回累计分钟数
        // - freshCount > 0：仍有无法触达的新鲜橘子，返回 -1
        return freshCount == 0 ? minutes : -1;
    }
}

java

🎯 解题关键点#

就像处理仓库里的水果：

先统计现状：
- 有多少新鲜橘子
- 哪些位置已经腐烂
模拟腐烂过程：
- 每分钟所有腐烂橘子同时发挥”作用”
- 用队列记录每一轮新腐烂的橘子
终止条件：
- 要么所有橘子都腐烂（返回时间）
- 要么有橘子永远不会腐烂（返回-1）

📊 复杂度分析#

时间复杂度：O(M × N)

M和N是网格的行数和列数
每个格子最多被访问一次

空间复杂度：O(M × N)

最坏情况：所有橘子都腐烂
队列可能需要存储所有格子的坐标

🎯 面试官最爱追问#

Q：如何优化空间复杂度？ A：实际上这是最优解了，因为我们必须追踪每个腐烂的橘子
Q：如果橘子是3D放置的呢？ A：只需将方向数组改为六个方向（上下左右前后）
Q：如何输出每个橘子腐烂的具体时间？ A：可以用一个额外的二维数组记录时间戳

💡 举一反三#

这个BFS模板还可以用在：

迷宫最短路径问题
僵尸感染问题
单词演变问题
细胞扩散问题

🎁 思考题#

如果有些格子是”隔离区”（值为3），腐烂不能透过它传播，如何修改代码？

例如：
2 1 1    这里的3像墙一样
1 3 1    阻止腐烂传播
0 1 1

plaintext

如果你知道答案？欢迎在评论区留言～

📝 面试技巧#

回答这题时，建议这样组织语言：

先说明为什么选择BFS（时间维度的特点）
解释统计新鲜橘子的必要性
强调队列size的作用（区分不同时间层）