LeetCode #994腐烂橘子问题JS代码超时：排查无限循环原因

问题背景 #

我在使用JavaScript解决LeetCode #994《Rotting Oranges（腐烂橘子）》时遇到了超时错误，代码陷入无限循环，请求排查原因。

问题描述 #

给定一个m x n grid，每个单元格有三种值：

• 0：空单元格
• 1：新鲜橘子
• 2：腐烂橘子

每分钟，所有与腐烂橘子四向相邻的新鲜橘子会腐烂。需返回直到没有新鲜橘子为止的最小分钟数，若不可能则返回-1。

原代码 #

var orangesRotting = function(grid) {
    if(!grid) return -1;

    let q = [], rows = grid.length, cols = grid[0].length, fresh = 0, time = 0;
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

    for(let r = 0; r < rows; ++r){
        for(let c = 0; c < cols; ++c){
            if(grid[r][c] === 1) fresh += 1;
            if(grid[r][c] === 2) q.push([r,c]);
        }
    }

    while(q.length !== 0 || fresh > 0){
        for(let i = 0; i < q.length; ++i){
            const [currRow,currCol] = q.shift();

            for(const [dirRow,dirCol] of dirs){
                const [newRow,newCol] = [currRow+dirRow,currCol+dirCol];

                if(newRow < 0 || newRow === grid.length || newCol < 0 || newCol === grid[0].length || grid[newRow][newCol] !== 1) continue;
                grid[newRow][newCol] = 2;
                fresh -= 1;
                q.push([newRow,newCol]);
            }
        }
        time += 1;
    }

    return fresh > 0 ? -1 : time;
};

错误原因分析 #

1. 无限循环根源：while循环条件q.length !== 0 || fresh > 0存在逻辑漏洞。当存在无法被感染的新鲜橘子（fresh>0）且队列已空（没有可扩散的腐烂橘子）时，条件变为false || true，循环会持续执行——内层for循环因队列为空什么都不做，time不断累加但fresh永远不会减少，最终触发超时。
2. BFS层级处理错误：内层for循环直接用q.length作为循环上限，但每次shift()会缩短队列长度，导致同一时间层的腐烂橘子没有被完整处理，时间统计不准确。

修复后的代码 #

var orangesRotting = function(grid) {
    if (!grid || grid.length === 0) return -1;

    let q = [], rows = grid.length, cols = grid[0].length, fresh = 0, time = 0;
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

    // 初始化：统计新鲜橘子数量，将所有腐烂橘子加入队列
    for(let r = 0; r < rows; ++r){
        for(let c = 0; c < cols; ++c){
            if(grid[r][c] === 1) fresh += 1;
            if(grid[r][c] === 2) q.push([r,c]);
        }
    }

    // 仅当队列有可扩散的腐烂橘子且还有新鲜橘子时，才继续循环
    while(q.length > 0 && fresh > 0){
        // 记录当前层的节点数，确保只处理当前分钟的腐烂橘子
        const levelSize = q.length;
        for(let i = 0; i < levelSize; ++i){
            const [currRow,currCol] = q.shift();

            for(const [dirRow,dirCol] of dirs){
                const newRow = currRow + dirRow;
                const newCol = currCol + dirCol;

                // 检查边界和是否为新鲜橘子
                if(newRow >= 0 && newRow < rows && newCol >=0 && newCol < cols && grid[newRow][newCol] === 1){
                    grid[newRow][newCol] = 2;
                    fresh -= 1;
                    q.push([newRow,newCol]);
                }
            }
        }
        // 处理完当前时间层，时间加1
        time += 1;
    }

    // 若仍有新鲜橘子，说明无法全部腐烂，返回-1；否则返回时间
    return fresh > 0 ? -1 : time;
};

修复说明 #

• 修正循环条件：改为while(q.length > 0 && fresh > 0)，从根源避免无限循环，只有当有可扩散的腐烂橘子且存在新鲜橘子时才继续执行。
• 固定层级节点数：用levelSize记录当前队列的初始长度，确保每次循环只处理同一时间层的所有腐烂橘子，保证BFS的层级遍历逻辑正确，时间统计准确。
• 优化边界判断：调整条件写法，逻辑更清晰直观。

内容的提问来源于stack exchange，提问作者Daniel_Kamel