給定一個
m x n的矩陣heights代表島嶼各位置的高度。水可以從高處往低處或等高處流動。太平洋在左邊和上邊，大西洋在右邊和下邊。找出所有能同時流向兩個大洋的座標。
Example:
Input: 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]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Intuition
TIP
反向思考：從海洋邊界出發逆流而上（往高處走），能到達的格子就是能流向該海洋的格子。兩個集合的交集即答案。
- 正向（從每個格子往海洋流）會有大量重複計算
- 反向從太平洋邊界和大西洋邊界各做一次 DFS/BFS
- 兩次搜尋都能到達的格子就是答案
Approaches
1. BFS (from Border) — O(m * n) / O(m * n)
- Idea: 從太平洋和大西洋的邊界各做一次 BFS，逆流而上標記可達格子
- Time:
O(m * n) - Space:
O(m * n)
class Solution {
fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
val m = heights.size
val n = heights[0].size
val pacific = Array(m) { BooleanArray(n) }
val atlantic = Array(m) { BooleanArray(n) }
val dirs = intArrayOf(0, 1, 0, -1, 0)
fun bfs(starts: List<IntArray>, reachable: Array<BooleanArray>) {
val queue: ArrayDeque<IntArray> = ArrayDeque()
for (s in starts) {
reachable[s[0]][s[1]] = true
queue.add(s)
}
while (queue.isNotEmpty()) {
val (r, c) = queue.removeFirst()
for (d in 0 until 4) {
val nr = r + dirs[d]
val nc = c + dirs[d + 1]
if (nr in 0 until m && nc in 0 until n &&
!reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
reachable[nr][nc] = true
queue.add(intArrayOf(nr, nc))
}
}
}
}
val pacStarts = mutableListOf<IntArray>()
val atlStarts = mutableListOf<IntArray>()
for (i in 0 until m) {
pacStarts.add(intArrayOf(i, 0))
atlStarts.add(intArrayOf(i, n - 1))
}
for (j in 0 until n) {
pacStarts.add(intArrayOf(0, j))
atlStarts.add(intArrayOf(m - 1, j))
}
bfs(pacStarts, pacific)
bfs(atlStarts, atlantic)
val result = mutableListOf<List<Int>>()
for (i in 0 until m) {
for (j in 0 until n) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(listOf(i, j))
}
}
}
return result
}
}⭐ 2. DFS (from Border) — O(m * n) / O(m * n)
- Idea: 從兩個海洋邊界各做一次 DFS，逆流而上標記，取交集
- Time:
O(m * n) - Space:
O(m * n)
class Solution {
fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
val m = heights.size
val n = heights[0].size
val pacific = Array(m) { BooleanArray(n) }
val atlantic = Array(m) { BooleanArray(n) }
fun dfs(r: Int, c: Int, reachable: Array<BooleanArray>, prevHeight: Int) {
if (r < 0 || r >= m || c < 0 || c >= n) return
if (reachable[r][c] || heights[r][c] < prevHeight) return
reachable[r][c] = true
dfs(r + 1, c, reachable, heights[r][c])
dfs(r - 1, c, reachable, heights[r][c])
dfs(r, c + 1, reachable, heights[r][c])
dfs(r, c - 1, reachable, heights[r][c])
}
for (i in 0 until m) {
dfs(i, 0, pacific, heights[i][0])
dfs(i, n - 1, atlantic, heights[i][n - 1])
}
for (j in 0 until n) {
dfs(0, j, pacific, heights[0][j])
dfs(m - 1, j, atlantic, heights[m - 1][j])
}
val result = mutableListOf<List<Int>>()
for (i in 0 until m) {
for (j in 0 until n) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(listOf(i, j))
}
}
}
return result
}
}🔑 Takeaways
- Pattern: 邊界反向搜尋 — 從終點倒推比從每個起點正向搜尋更高效
- Key trick: 逆流條件是
heights[nr][nc] >= heights[r][c]；兩次搜尋的交集即答案