题目
有一个 m × n 的矩形岛屿，与太平洋和大西洋相邻。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights， heights[r][c] 表示坐标 (r, c) 上单元格高于海平面的高度。
岛上雨水较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (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] <= 105
题目来源：LeetCode
分析
我们知道，雨水是从高往低处流的，题目意思，对于每一个单元格，如果它旁边的单元格高度比它小，那么当前单元格的雨水可以流向高度低的单元格。按照这样的流向规则，如果从一个单元格开始，它的雨水通过高处往低处流的方向，既可以流向大西洋，也可以流向太平洋，那么这个单元格是满足条件的，即将此单元格位置添加到答案中。
按照正常思维，模拟雨水的流动，我们一般是从一个单元格开始，一直往旁边的单元格搜索，判断是否比当前单元格高度低，直到无法继续前进，或者可以流向海洋。但是这种算法会重复遍历每个单元格，时间复杂度太高。
采用逆向思维，我们从可以流向海洋的单元格，即矩阵的四个边界的单元格，开始反向搜索雨水可以流向边界的单元格。反向搜索时，每次只能移动到高度相同或更大的单元格，对于搜索过的单元格做标记，代表此单元格可以流向海洋。
搜索的算法可以采用深度优先搜索算法，或者广度优先搜索算法。
从矩阵的左边界和上边界的单元格开始反向搜索过的单元格，是可以流向太平洋的。从矩阵的右边界和下边界的单元格开始反向搜索过的单元格，是可以流向大西洋的。
最后，我们遍历每个单元格，如果它既可以从太平洋反向到达也可以从大西洋反向到达，那么将此单元格位置添加到答案中。
实现
package com.chenpi.no0417PacificAtlantic;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author 陈皮
* @version 1.0
* @description
* @date 2022/4/27
*/
public class No0417PacificAtlantic {
public static void main(String[] args) {
No0417PacificAtlantic inst = new No0417PacificAtlantic();
int[][] 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}};
// int[][] heights = {{2, 1}, {1, 2}};
System.out.println(inst.pacificAtlantic(heights));
}
// 代表四个方向
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length;
int n = heights[0].length;
// true代表此位置可以流向太平洋
boolean[][] pacific = new boolean[m][n];
// true代表此位置可以流向大西洋
boolean[][] atlantic = new boolean[m][n];
// 最左边一排的每一个位置开始，深度优先搜索可以流向太平洋的位置
for (int i = 0; i < m; i++) {
dfs(heights, i, 0, pacific);
}
// 最上面一排的每一个位置开始，深度优先搜索可以流向太平洋的位置
for (int j = 1; j < n; j++) {
dfs(heights, 0, j, pacific);
}
// 最右边一排的每一个位置开始，深度优先搜索可以流向大西洋的位置
for (int i = 0; i < m; i++) {
dfs(heights, i, n - 1, atlantic);
}
// 最下面一排的每一个位置开始，深度优先搜索可以流向大西洋的位置
for (int j = 0; j < n - 1; j++) {
dfs(heights, m - 1, j, atlantic);
}
// 遍历每一个位置，如果能可以同时流向大西洋和太平洋，即满足条件
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(Arrays.asList(i, j));
}
}
}
return result;
}
public void dfs(int[][] heights, int row, int col, boolean[][] ocean) {
// 标记过，停止向前搜索
if (ocean[row][col]) {
return;
}
int m = heights.length;
int n = heights[0].length;
ocean[row][col] = true;
// 向四个方向搜索
for (int[] dir : dirs) {
int newRow = row + dir[0], newCol = col + dir[1];
// 下一个位置比当前位置高，则继续深度搜索
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
&& heights[newRow][newCol] >= heights[row][col]) {
dfs(heights, newRow, newCol, ocean);
}
}
}
}
// 输出结果如下
[[0, 0], [0, 1], [1, 0], [1, 1]]
Leetcode 执行结果：
本次分享到此结束啦~~
如果觉得文章对你有帮助，点赞、收藏、关注、评论，您的支持就是我创作最大的动力！
