Medium
题目描述
有一个 m x 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]]
解释: 以下单元格可以流向太平洋和大西洋，如下所示：
[0,4]: [0,4] -> 太平洋
[0,4] -> 大西洋
[1,3]: [1,3] -> [0,3] -> 太平洋
[1,3] -> [1,4] -> 大西洋
...
示例 2：
输入: heights = [[1]]
输出: [[0,0]]
解释: 水可以从唯一的单元格流向太平洋和大西洋。
提示：
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
解题思路
解题思路
这道题的关键在于理解水流的规律：水只能从高处流向低处或同等高度的位置。
暴力解法：对每个单元格分别进行DFS/BFS，检查是否能同时到达两个海洋。时间复杂度O(m²n²)，效率较低。
逆向思维（推荐）：换个角度思考，从海洋开始逆流而上。水能从海洋流到一个单元格，说明该单元格的水也能流向海洋。
具体步骤：
- 从太平洋边界（第一行和第一列）开始DFS，找到所有能流向太平洋的单元格
- 从大西洋边界（最后一行和最后一列）开始DFS，找到所有能流向大西洋的单元格
- 找到两个集合的交集，即既能流向太平洋又能流向大西洋的单元格
在逆向DFS中，只有当相邻单元格高度大于等于当前单元格时，水才能逆流到相邻单元格。
这种方法的优势是每个单元格最多被访问两次（分别被两个海洋的DFS访问），时间复杂度降为O(mn)。
代码实现
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
// 从太平洋边界开始DFS
for (int i = 0; i < m; i++) {
dfs(heights, pacific, i, 0, heights[i][0]);
}
for (int j = 0; j < n; j++) {
dfs(heights, pacific, 0, j, heights[0][j]);
}
// 从大西洋边界开始DFS
for (int i = 0; i < m; i++) {
dfs(heights, atlantic, i, n - 1, heights[i][n - 1]);
}
for (int j = 0; j < n; j++) {
dfs(heights, atlantic, m - 1, j, heights[m - 1][j]);
}
// 找到交集
vector<vector<int>> result;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.push_back({i, j});
}
}
}
return result;
}
private:
void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int i, int j, int prevHeight) {
int m = heights.size(), n = heights[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || heights[i][j] < prevHeight) {
return;
}
visited[i][j] = true;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto& dir : dirs) {
dfs(heights, visited, i + dir[0], j + dir[1], heights[i][j]);
}
}
};
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
pacific = [[False] * n for _ in range(m)]
atlantic = [[False] * n for _ in range(m)]
def dfs(visited, i, j, prev_height):
if (i < 0 or i >= m or j < 0 or j >= n or
visited[i][j] or heights[i][j] < prev_height):
return
visited[i][j] = True
for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
dfs(visited, i + di, j + dj, heights[i][j])
# 从太平洋边界开始DFS
for i in range(m):
dfs(pacific, i, 0, heights[i][0])
for j in range(n):
dfs(pacific, 0, j, heights[0][j])
# 从大西洋边界开始DFS
for i in range(m):
dfs(atlantic, i, n - 1, heights[i][n - 1])
for j in range(n):
dfs(atlantic, m - 1, j, heights[m - 1][j])
# 找到交集
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
public class Solution {
public IList<IList<int>> PacificAtlantic(int[][] heights) {
int m = heights.Length, n = heights[0].Length;
bool[,] pacific = new bool[m, n];
bool[,] atlantic = new bool[m, n];
// 从太平洋边界开始DFS
for (int i = 0; i < m; i++) {
DFS(heights, pacific, i, 0, heights[i][0]);
}
for (int j = 0; j < n; j++) {
DFS(heights, pacific, 0, j, heights[0][j]);
}
// 从大西洋边界开始DFS
for (int i = 0; i < m; i++) {
DFS(heights, atlantic, i, n - 1, heights[i][n - 1]);
}
for (int j = 0; j < n; j++) {
DFS(heights, atlantic, m - 1, j, heights[m - 1][j]);
}
// 找到交集
IList<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i, j] && atlantic[i, j]) {
result.Add(new List<int> { i, j });
}
}
}
return result;
}
private void DFS(int[][] heights, bool[,] visited, int i, int j, int prevHeight) {
int m = heights.Length, n = heights[0].Length;
if (i < 0 || i >= m || j < 0 || j >= n || visited[i, j] || heights[i][j] < prevHeight) {
return;
}
visited[i, j] = true;
int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int d = 0; d < 4; d++) {
DFS(heights, visited, i + dirs[d, 0], j + dirs[d, 1], heights[i][j]);
}
}
}
var pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length;
const pacific = Array(m).fill().map(() => Array(n).fill(false));
const atlantic = Array(m).fill().map(() => Array(n).fill(false));
function dfs(visited, i, j, prevHeight) {
if (i < 0 || i >= m || j < 0 || j >= n ||
visited[i][j] || heights[i][j] < prevHeight) {
return;
}
visited[i][j] = true;
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [di, dj] of dirs) {
dfs(visited, i + di, j + dj, heights[i][j]);
}
}
// 从太平洋边界开始DFS
for (let i = 0; i < m; i++) {
dfs(pacific, i, 0, heights[i][0]);
}
for (let j = 0; j < n; j++) {
dfs(pacific, 0, j, heights[0][j]);
}
// 从大西洋边界开始DFS
for (let i = 0; i < m; i++) {
dfs(atlantic, i, n - 1, heights[i][n - 1]);
}
for (let j = 0; j < n; j++) {
dfs(atlantic, m - 1, j, heights[m - 1][j]);
}
// 找到交集
const result = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.push([i, j]);
}
}
}
return result;
};
复杂度分析
| 复杂度类型 | 大小 | 说明 |
|---|---|---|
| 时间复杂度 | O(mn) | 每个单元格最多被访问两次（分别被两个海洋的DFS访问） |
| 空间复杂度 | O(mn) | 需要两个二维数组记录访问状态，递归栈深度最坏情况下为O(mn) |