Leetcode 417题：太平洋和大西洋水流问题，如何高效求解？

本文共计1049个文字，预计阅读时间需要5分钟。

逆向思维，设想海水上涨的时刻，太平洋和大西洋的水位能漫到陆地的最高点是多少，分别记录下来。设想海水在达到最高点后不再继续上涨。此时，分别记录下太平洋和大西洋的水位能达到的高度。

逆向思维，假设海水涨潮的时候，太平洋和大西洋的水能漫到陆地的最高点是多少，分别记录下来。假设水在到达最高点后不在继续漫了。这时分别记录下太平洋和大西洋的水能到达的位置。再取他们公共的部分就是答案了。 一、题目大意

标签: 搜索

leetcode.cn/problems/pacific-atlantic-water-flow

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

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

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

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