生鲜电商最讨厌的算法题：腐烂的橘子
各位算法忍者们，欢迎来到忍者算法。今天要聊的这道题，让我想起了在生鲜电商实习时的一个场景...
🍊 从生鲜仓库说起
产品经理："我们仓库里有一批橘子，已经发现有几个坏掉了。假设每天坏橘子会污染它周围的新鲜橘子，我们需要预估多少天后所有橘子会坏掉，这样才能及时调整库存..."
听起来是不是很像LeetCode 994题？
💡 问题的本质
这道题是这样描述的：
在一个 N × M 的网格中，每个单元格有三种可能的值：
- 0 表示空格子
- 1 表示新鲜橘子
- 2 表示腐烂的橘子
每分钟，腐烂的橘子会让上、下、左、右四个方向的新鲜橘子腐烂。
求需要多少分钟，整个网格中的橘子都会腐烂？如果不可能全部腐烂，返回 -1。
示例：
输入：[
[2,1,1],
[1,1,0],
[0,1,1]
]
输出：4🤔 第一反应可能是DFS？
很多同学看到网格搜索就想到DFS（深度优先搜索）。但等等，这题有个关键词：时间！
想象一下腐烂过程：
- 第0分钟：初始状态，有些橘子已经腐烂
- 第1分钟：这些腐烂橘子同时感染周围的橘子
- 第2分钟：新腐烂的橘子又同时感染周围的...
这不就是**广度优先搜索(BFS)**的经典场景吗？
⚡ 代码实现：BFS的完美运用
java
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int freshCount = 0; // 新鲜橘子计数
// 第一步：找到所有腐烂的橘子，入队
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;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int minutes = 0;
// 开始BFS
while (!queue.isEmpty() && freshCount > 0) {
minutes++; // 时间+1
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];
// 检查边界和是否是新鲜橘子
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
grid[newRow][newCol] == 1) {
grid[newRow][newCol] = 2; // 感染这个橘子
queue.offer(new int[]{newRow, newCol});
freshCount--; // 新鲜橘子-1
}
}
}
}
// 如果还有新鲜橘子，返回-1
return freshCount == 0 ? minutes : -1;
}
}🎯 解题关键点
就像处理仓库里的水果：
先统计现状：
- 有多少新鲜橘子
- 哪些位置已经腐烂
模拟腐烂过程：
- 每分钟所有腐烂橘子同时发挥"作用"
- 用队列记录每一轮新腐烂的橘子
终止条件：
- 要么所有橘子都腐烂（返回时间）
- 要么有橘子永远不会腐烂（返回-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如果你知道答案？欢迎在评论区留言～
📝 面试技巧
回答这题时，建议这样组织语言：
- 先说明为什么选择BFS（时间维度的特点）
- 解释统计新鲜橘子的必要性
- 强调队列size的作用（区分不同时间层）
作者：忍者算法
公众号：忍者算法
🎯 回复【刷题清单】获取更多BFS经典题目解析 👥 回复【加群】加入算法/面试交流群，一起学习进步 🧑💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现
#算法面试 #LeetCode #BFS #面试高频题