太平洋大西洋水流问题

难度: Medium

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [r_i, c_i] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：

输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10⁵

Submission

运行时间: 73 ms

内存: 17.5 MB

class Solution:
    # 逆向思维 水从高处往低处流  
    # 那我从太平洋沿岸的点向内搜寻，找比自己高的点，逆流而上(也就是从内部往沿岸顺流而下逆过程)
    # 最后能标记到的访问的点 也就是能流到太平洋的点
    # 大西洋同理 最后找两个都标记的，就是满足要求的
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        result = []
        # 方向
        self.dirs = [(-1,0),(0,1),(1,0),(0,-1)]
        row = len(heights)
        col = len(heights[0])
        # 能流到太平洋的点
        pacific_visited = [[0] * col for _ in range(row)]
        # 能流到大西洋的点
        altantic_visited = [[0] * col for _ in range(row)]
        for i in range(row):
            # 对每一行遍历 太平洋遍历最左侧的列  大西洋遍历最右侧的列
            self.dfs(pacific_visited, i, 0, heights)
            self.dfs(altantic_visited, i, col-1, heights)
        for j in range(col):
            # 对每一列遍历 太平洋遍历最上侧的行  大西洋遍历最下侧的行
            self.dfs(pacific_visited, 0, j, heights)
            self.dfs(altantic_visited, row-1, j, heights)
        # 然后看看那些点可以流过两个海洋 就是要找的点
        for i in range(row):
            for j in range(col):
                if pacific_visited[i][j] and altantic_visited[i][j]:
                    result.append([i,j])
        return result

    
    def dfs(self, visited, cur_x, cur_y, heights):
        # 这里可以及时return 因为main函数主动调用时可能存在已访问的 本函数肯定不会
        if visited[cur_x][cur_y]:
            return
        visited[cur_x][cur_y] = 1
        for d in self.dirs:
            new_x, new_y = cur_x + d[0], cur_y + d[1]
            # 合法性检查
            if new_x >=0 and new_x < len(heights) and new_y >=0 and new_y < len(heights[0]):
                # 没访问过并且 比本节点高 才是逆流而上
                if not visited[new_x][new_y] and heights[new_x][new_y] >= heights[cur_x][cur_y]:
                    self.dfs(visited, new_x, new_y, heights)

Explain

该题解采用逆向思维的方式。水从高处往低处流，那么可以从太平洋和大西洋的沿岸点开始向内搜寻，找到比自己高的点，逆流而上。对于每个海洋，分别从行和列的边界开始深度优先搜索，标记能够到达该海洋的点。最后找到既能流到太平洋又能流到大西洋的点，即为满足要求的结果。

时间复杂度: O(mn)

空间复杂度: O(mn)

class Solution:
    # 逆向思维 水从高处往低处流  
    # 那我从太平洋沿岸的点向内搜寻，找比自己高的点，逆流而上(也就是从内部往沿岸顺流而下逆过程)
    # 最后能标记到的访问的点 也就是能流到太平洋的点
    # 大西洋同理 最后找两个都标记的，就是满足要求的
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        result = []
        # 方向
        self.dirs = [(-1,0),(0,1),(1,0),(0,-1)]
        row = len(heights)
        col = len(heights[0])
        # 能流到太平洋的点
        pacific_visited = [[0] * col for _ in range(row)]
        # 能流到大西洋的点
        altantic_visited = [[0] * col for _ in range(row)]
        for i in range(row):
            # 对每一行遍历 太平洋遍历最左侧的列  大西洋遍历最右侧的列
            self.dfs(pacific_visited, i, 0, heights)
            self.dfs(altantic_visited, i, col-1, heights)
        for j in range(col):
            # 对每一列遍历 太平洋遍历最上侧的行  大西洋遍历最下侧的行
            self.dfs(pacific_visited, 0, j, heights)
            self.dfs(altantic_visited, row-1, j, heights)
        # 然后看看那些点可以流过两个海洋 就是要找的点
        for i in range(row):
            for j in range(col):
                if pacific_visited[i][j] and altantic_visited[i][j]:
                    result.append([i,j])
        return result

    
    def dfs(self, visited, cur_x, cur_y, heights):
        # 这里可以及时return 因为main函数主动调用时可能存在已访问的 本函数肯定不会
        if visited[cur_x][cur_y]:
            return
        # 标记当前节点已访问
        visited[cur_x][cur_y] = 1
        # 向四个方向遍历
        for d in self.dirs:
            new_x, new_y = cur_x + d[0], cur_y + d[1]
            # 合法性检查
            if new_x >=0 and new_x < len(heights) and new_y >=0 and new_y < len(heights[0]):
                # 没访问过并且 比本节点高 才是逆流而上
                if not visited[new_x][new_y] and heights[new_x][new_y] >= heights[cur_x][cur_y]:
                    self.dfs(visited, new_x, new_y, heights)

Explore

在太平洋大西洋水流问题中，采用逆向思维策略是因为直接模拟水从高处向低处流动的过程在实现上较为复杂，且难以直接确定流向两个大洋的起点。从海洋边缘单元格开始向内部逆流搜索可以简化问题，因为边缘单元格自然与海洋相连，只需要检查能够逆流到达边缘单元格的内陆单元格。这样可以有效地标记出所有可以流入特定大洋的单元格，从而简化问题解决过程。

在逆向思维的策略中，从海洋边缘向内部进行搜索时，我们模拟的是水从低处向高处的逆流过程。因此，只有当一个相邻单元格的高度大于或等于当前单元格的高度时，水才可能从该相邻单元格流向当前单元格。这种策略确保了我们正确地模拟了水流的逆流路径，避免了错误地将水流向实际上无法到达的更低的区域。

在本题策略中，即使已访问的单元格高度小于当前单元格，也无需重新访问。由于我们从海洋边缘向内部逆流搜索，标记过程中已经保证了只有那些能够通过逆流到达边缘单元格的路径被标记。因此，如果一个单元格在之前已被标记为可访问，即意味着已确定它可以流向对应的大洋，无论从哪条路径到达。重复访问已标记的更低单元格并不会提供新的信息，因为水不会从低处自动流向更高处。

题解中提到的递归深度`min(m, n)`可能是基于最优或平均情况的考虑，假设水流从一边缘逐步向另一边缘流动，且每次都能向内延伸一行或一列。然而，实际上在最坏情况下，递归深度可以更大，尤其是当矩阵中的高度配置允许水流在复杂路径中循环移动时。理论上，递归深度可以达到`m * n`，尤其是在一个高度差异极小且布局复杂的矩阵中。