LeetCode 994. 腐烂的橘子

约 6 分钟
文章信息 16 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 LeetCode 75 LeetCode 热题 100 腾讯 字节 阿里 华为 微软 拼多多 小米 小红书 滴滴
标签
数组 广度优先搜索 矩阵

题目描述

✅ 994. 腐烂的橘子

image-20260928223629721

image-20260928223629722

题意分析

网格中 0 是空格，1 是新鲜橘子，2 是腐烂橘子。每分钟，所有腐烂橘子同时使上下左右相邻的新鲜橘子腐烂。求不再有新鲜橘子所需的最少分钟数；无法全部感染返回 -1，初始没有新鲜橘子返回 0。

解法：多源 BFS 分层扩散

核心思路

[!blue]

把橘子看成节点，相邻橘子之间连一条边，每经过一条边需要一分钟。一个新鲜橘子最早腐烂的时间，就是它到任意初始腐烂橘子的最短距离。所有初始腐烂橘子同时入队作为第 0 层，多源 BFS 按距离递增访问，第一次感染便是最早可能的时间。

每轮开始固定队列长度 size，只处理这一层。处理过程中感染的新橘子加到队尾，留到下一分钟继续传播；整层处理完才增加 minutes。这样一次循环恰好表示经过一分钟，最后一批新鲜橘子被感染时的分钟数就是答案。

用 fresh 记录剩余新鲜橘子的数量。发现新鲜邻居时立即改为 2、减少 fresh 再入队，既标记已访问，也避免多个来源重复感染同一格。循环同时要求 fresh > 0，因此全部感染后不会再多处理一层；若队列耗尽仍有新鲜橘子，说明它们不可达。

解题步骤

  1. 扫描网格：新鲜橘子计入 fresh，所有腐烂橘子加入队列。
  2. 当队列非空且 fresh > 0 时，记录当前队列长度 size，它就是本分钟参与扩散的橘子数。
  3. 弹出恰好 size 个格子，检查四个方向；越界、空格和已腐烂格都跳过，新鲜邻居立即标记为 2、减少 fresh 并入队。
  4. 当前层处理完后令 minutes++。
  5. 循环结束后，若 fresh == 0 返回分钟数，否则返回 -1。

代码实现

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int fresh = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    fresh++;
                } else if (grid[r][c] == 2) {
                    queue.offer(new int[] {
                        r,
                        c
                    });
                }
            }
        }

        int minutes = 0;
        int[][] dirs = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1},
        };

        while (!queue.isEmpty() && fresh > 0) {
            // 同一层同时扩散，新感染的橘子留到下一分钟。
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();

                for (int[] dir : dirs) {
                    int nr = cur[0] + dir[0];
                    int nc = cur[1] + dir[1];

                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1) {
                        continue;
                    }

                    // 入队前立即感染并减少鲜橘子，其他邻居就不会重复处理。
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.offer(new int[] {
                        nr,
                        nc
                    });
                }
            }

            minutes++;
        }

        return fresh == 0 ? minutes : -1;
    }
}

func orangesRotting(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])
    queue := make([][2]int, 0)
    fresh := 0

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 1 {
                fresh++
            } else if grid[r][c] == 2 {
                queue = append(queue, [2]int{
                    r,
                    c,
                })
            }
        }
    }

    dirs := [][]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }
    minutes := 0
    for len(queue) > 0 && fresh > 0 {
        // 同一层同时扩散，新感染的橘子留到下一分钟。
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            for _, dir := range dirs {
                nr := cur[0] + dir[0]
                nc := cur[1] + dir[1]
                if nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1 {
                    continue
                }
                // 入队前立即感染并减少鲜橘子，其他邻居就不会重复处理。
                grid[nr][nc] = 2
                fresh--
                queue = append(queue, [2]int{
                    nr,
                    nc,
                })
            }
        }
        minutes++
    }
    if fresh == 0 {
        return minutes
    }
    return -1
}

复杂度分析

  • 时间复杂度：$O(mn)$，其中 m、n 为网格行列数。初始化扫描所有格子，每个橘子至多入队一次，出队后只检查四个方向。
  • 空间复杂度：$O(mn)$，最坏情况下队列可同时保存整张网格中的格子。

关键点总结

[!green]

  • 同时从所有腐烂橘子出发，BFS 才能求出每个新鲜橘子到最近感染源的距离。
  • 固定每层大小模拟同时传播，最后完成感染的那一层决定总时间。
  • 原地把 1 改成 2 可同时表示感染和访问，无需额外 visited。

易错点总结

[!yellow]

  • 初始没有新鲜橘子时直接得到 0；有新鲜橘子但没有腐烂橘子时，队列为空，返回 -1。
  • 不固定 size 会在同一轮继续处理新入队节点，把多分钟传播压成一分钟。
  • 循环不加 fresh > 0，可能在全部感染后多处理最后一层，分钟数多 1。
  • 感染后不立即改成 2，会被其他相邻橘子重复入队并重复减少 fresh。
  • 空格不能传播感染。BFS 结束后必须检查 fresh，队列为空也可能是剩余新鲜橘子被空格隔开。

相似题目

题目 难度 关联与区别
542. 01 矩阵 中等 同样从多个源同时BFS，本题最终取感染时间最大值并检测是否仍有不可达目标。
286. 墙与门 中等 同样在障碍网格上传播最近源距离，本题源是所有初始腐烂橘子。
1162. 地图分析 中等 从多个起点同时进行逐层广度优先搜索；本题模拟腐烂波及相邻橘子的分钟数，该题从全部陆地求海洋的最近距离。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/72302154
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！