LeetCode 太平洋大西洋水流题解

LeetCode 太平洋大西洋水流题解

题目描述

给定一个 m x n 的高度矩阵，太平洋在大西洋的左侧和上方。找到所有能够流到太平洋和大西洋的单元格。

示例：

输入：matrix = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,3],[6,7,1,4,5],[5,1,1,2,4]]
输出：[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

解题思路

方法：BFS

思路：

• 使用 BFS 从太平洋和大西洋的边界分别开始搜索。
• 记录能够流到太平洋和大西洋的单元格。
• 返回两者的交集。

复杂度分析：

• 时间复杂度：O(m * n)。
• 空间复杂度：O(m * n)。

代码实现

from collections import deque def pacific_atlantic(matrix): if not matrix: return [] m, n = len(matrix), len(matrix[0]) pacific = [[False] * n for _ in range(m)] atlantic = [[False] * n for _ in range(m)] def bfs(visited): queue = deque() for i in range(m): queue.append((i, 0)) for j in range(n): queue.append((0, j)) while queue: i, j = queue.popleft() if visited[i][j]: continue visited[i][j] = True for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]: ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj] and matrix[ni][nj] >= matrix[i][j]: queue.append((ni, nj)) bfs(pacific) bfs(atlantic) result = [] for i in range(m): for j in range(n): if pacific[i][j] and atlantic[i][j]: result.append([i, j]) return result # 测试 def test_pacific_atlantic(): matrix = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 3], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]] print(pacific_atlantic(matrix)) if __name__ == "__main__": test_pacific_atlantic()

总结

太平洋大西洋水流是 BFS 的典型应用，从两个大洋的边界开始搜索，找出所有能够流到两个大洋的单元格。