Leetcode 417太平洋大西洋水流问题BFS超时排查求助

问题背景 #

给定m×n的岛屿矩阵，左、上边界邻接太平洋，右、下边界邻接大西洋。矩阵中heights[r][c]表示(r,c)单元格的海拔高度，雨水可流向海拔≤当前单元格的相邻（上下左右）单元格，邻接海洋的单元格可直接流入海洋。需返回所有能同时流向太平洋和大西洋的单元格坐标列表。

代码超时核心原因 #

• 队列操作效率极低：你的BFS中使用Q.pop(0)取出队首元素，列表的pop(0)是O(n)时间复杂度（需移动后续所有元素），大规模矩阵下会导致时间急剧飙升，这是超时的主要诱因。
• 遍历条件完全写反：当前判断条件heights[x][y] > heights[next_x][next_y]不符合反向遍历逻辑。我们是从海洋边界反向寻找能流到海洋的单元格，正确逻辑应为：下一个单元格海拔≥当前单元格（即该单元格的水可以流到当前单元格，进而流入海洋）。原条件会漏标大量节点，同时可能触发不必要的遍历，加剧超时。
• 函数参数不匹配：定义的bfs函数仅接受node和visited两个参数，但调用时传入了三个参数（如bfs((row, col), pacific_visited, 0)），虽未直接报错，但属于代码逻辑漏洞。

修正后的代码 #

from collections import deque

class Solution:
    def pacificAtlantic(self, heights):
        if not heights or not heights[0]:
            return []
        
        rows, cols = len(heights), len(heights[0])
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        
        def bfs(start_nodes):
            visited = [[False]*cols for _ in range(rows)]
            q = deque(start_nodes)
            # 提前标记所有边界起始节点
            for x, y in start_nodes:
                visited[x][y] = True
            
            while q:
                x, y = q.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols:
                        if not visited[nx][ny] and heights[nx][ny] >= heights[x][y]:
                            visited[nx][ny] = True
                            q.append((nx, ny))
            return visited
        
        # 太平洋起始节点：上边界 + 左边界（排除重复的左上角）
        pacific_starts = [(0, i) for i in range(cols)] + [(i, 0) for i in range(1, rows)]
        pacific_visited = bfs(pacific_starts)
        
        # 大西洋起始节点：下边界 + 右边界（排除重复的右下角）
        atlantic_starts = [(rows-1, i) for i in range(cols)] + [(i, cols-1) for i in range(rows-1)]
        atlantic_visited = bfs(atlantic_starts)
        
        # 筛选同时能流向两大洋的单元格
        result = []
        for i in range(rows):
            for j in range(cols):
                if pacific_visited[i][j] and atlantic_visited[i][j]:
                    result.append([i, j])
        return result

额外优化说明 #

• 改用collections.deque的popleft()方法，队列操作变为O(1)时间复杂度，大幅提升遍历效率。
• 调整BFS为接受起始节点列表，一次性初始化队列，避免多次调用BFS的重复开销。
• 增加空矩阵判断，提升代码鲁棒性。

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