复盘 · LC 994 腐烂的橘子

题目

题号：LeetCode 994
名称：腐烂的橘子（Rotting Oranges）
难度：Medium
链接：leetcode.cn/problems/rotting-oranges
今日代码：994-腐烂的橘子/index.js

题意

m × n 网格：0 空、1 好橘子、2 坏橘子。每分钟，四向相邻的好橘子会被坏橘子传染。求全部变坏的最少分钟；若不可能，返回 -1。

初始可以有多颗坏橘子（多源同时扩散）。
没有好橘子时答案是 0。
边界：全空、只有好没有坏、坏在角落、好被空格隔开。

涉及算法

标签	一句话
多源 BFS	所有坏橘子同时入队，按层/按步扩散，最后一层步数即答案
矩阵搜索	四向合法坐标 + 原地把 `1` 改成 `2` 当访问标记

教程对照：11 · 队列与层序思想；和 200 岛屿同属网格扩散，本题强调多源 + 最短时间。

评价我的解法

你的思路：先收集全部坏橘子，再沿数组下标向前扩四邻，把好橘子改成坏并记下 step，最后扫一遍是否还有 1。这就是多源 BFS（用「边扫边 push」模拟队列），能 AC。

我的代码（摘自 994-腐烂的橘子/index.js，不含本地测例与提交统计注释）：

javascript

var orangesRotting = function (grid) {
  let xLen = grid[0].length;
  let yLen = grid.length;
  /* 记录坏橘子的数组 */
  const badOrangeArr = [];
  for (let i = 0; i < yLen; i++) {
    for (let j = 0; j < xLen; j++) {
      const item = grid[i][j];
      if (item === 2) {
        badOrangeArr.push({
          y: i,
          x: j,
          step: 0,
        });
      }
    }
  }

  /* 方向数组 */
  let direction = [
    {
      x: -1,
      y: 0,
    },
    {
      x: 1,
      y: 0,
    },
    {
      x: 0,
      y: 1,
    },
    {
      x: 0,
      y: -1,
    },
  ];

  /* 是否合法 */
  function isRightXY(x, y) {
    if (x >= xLen || x < 0 || y < 0 || y >= yLen) {
      return false;
    }
    return true;
  }

  let maxStep = 0;
  for (let i = 0; i < badOrangeArr.length; i++) {
    const item = badOrangeArr[i];
    console.log(item, i, "<===");
    for (let j = 0; j < direction.length; j++) {
      const newY = item.y + direction[j].y;
      const newX = item.x + direction[j].x;
      if (!isRightXY(newX, newY)) {
        continue;
      }
      const newVal = grid[newY][newX];
      if (newVal !== 1) {
        continue;
      }
      const newBadOrange = { y: newY, x: newX, step: item.step + 1 };
      grid[newY][newX] = 2;
      maxStep = Math.max(maxStep, newBadOrange.step);
      badOrangeArr.push(newBadOrange);
    }
  }

  for (let i = 0; i < yLen; i++) {
    for (let j = 0; j < xLen; j++) {
      if (grid[i][j] === 1) {
        return -1;
      }
    }
  }
  return maxStep;
};

对在哪、糙在哪：

多源起手正确：初始所有 2 入队，同时扩散，不会「只从一个坏橘子 BFS」算错时间。
for 扫增长数组：等价于队列 BFS，语义通；比误写成「只扫初始长度」要稳。
提交很慢（约 99ms / 5%）：循环里留了 console.log，评测环境每次输出都会拖垮用时——这是今天最大的「非算法」扣分。
结构偏重：方向用对象数组、每个格子包 {x,y,step}，内存约 64MB 也偏高；更常见是存坐标对、用「层长」记分钟。
xLen/yLen 命名：实际是列数/行数，和常见 m/n 或 rows/cols 反着说也行，但面试口述要统一「先 i 行再 j 列」。

小结：套路（多源 BFS）选对了，和 8-15 建议的延伸题对齐；清掉日志、改成层序计时后，复杂度观感会干净很多。

最佳题解

多源 BFS + 按层记分钟（无多余对象、无日志）：

javascript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const queue = [];
  let fresh = 0;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
      else if (grid[i][j] === 1) fresh++;
    }
  }

  if (fresh === 0) return 0;

  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let minutes = 0;
  let head = 0;

  while (head < queue.length && fresh > 0) {
    const size = queue.length - head;
    for (let k = 0; k < size; k++) {
      const [r, c] = queue[head++];
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] !== 1) {
          continue;
        }
        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc]);
      }
    }
    minutes++;
  }

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

时间 O(mn)，空间 O(mn) 队列最坏。
为何更优：一层一轮 minutes++，不必给每个格子挂 step；用 fresh 计数可提前结束，也省掉最后整表扫描；没有 console.log。

关联题目

题	为何相关
200. 岛屿数量	同网格四向；连通块 vs 传染时间
542. 01 矩阵	多源 BFS 求到最近 0 的距离
286. 墙与门	多源 BFS 填最短距离
1162. 地图分析	多源 BFS 求最远陆地到水

一句话带走

腐烂橘子：所有坏橘子一起入队做多源 BFS，按层计分钟；扩散完还有好橘子就 -1。提交前删掉调试输出。

复盘 · LC 994 腐烂的橘子 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​