給定一個
m x n的整數矩陣，找出最長遞增路徑的長度。每一步可以往上下左右四個方向移動，但下一格的值必須嚴格大於當前格。
Example:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 (路徑: 1 -> 2 -> 6 -> 9)
Intuition
TIP
從每個格子出發做 DFS，用記憶化避免重複計算；因為路徑嚴格遞增，不會有環。
- 從每個格子出發找最長遞增路徑，取所有起點的最大值
- 因為值嚴格遞增，所以不可能回頭，天然無環，適合記憶化搜尋
memo[i][j]記錄從 (i,j) 出發的最長遞增路徑長度
Approaches
1. DFS + Memoization — O(m * n) / O(m * n)
- Idea: 從每個格子出發做 DFS，用 memo 陣列快取結果，若 memo 已有值則直接回傳。
- Time:
O(m * n)，每個格子最多計算一次 - Space:
O(m * n)
class Solution {
private val dirs = intArrayOf(0, 1, 0, -1, 0)
fun longestIncreasingPath(matrix: Array<IntArray>): Int {
val m = matrix.size
val n = matrix[0].size
val memo = Array(m) { IntArray(n) }
var result = 0
for (i in 0 until m) {
for (j in 0 until n) {
result = maxOf(result, dfs(matrix, memo, i, j, m, n))
}
}
return result
}
private fun dfs(matrix: Array<IntArray>, memo: Array<IntArray>, i: Int, j: Int, m: Int, n: Int): Int {
if (memo[i][j] != 0) return memo[i][j]
var longest = 1
for (d in 0 until 4) {
val ni = i + dirs[d]
val nj = j + dirs[d + 1]
if (ni in 0 until m && nj in 0 until n && matrix[ni][nj] > matrix[i][j]) {
longest = maxOf(longest, 1 + dfs(matrix, memo, ni, nj, m, n))
}
}
memo[i][j] = longest
return longest
}
}⭐ 2. Topological Sort (BFS) — O(m * n) / O(m * n)
- Idea: 將矩陣看成 DAG，從「沒有更小鄰居的格子」（入度為 0）開始 BFS，逐層剝離，層數就是最長路徑。
- Time:
O(m * n) - Space:
O(m * n)
class Solution {
fun longestIncreasingPath(matrix: Array<IntArray>): Int {
val m = matrix.size
val n = matrix[0].size
val dirs = intArrayOf(0, 1, 0, -1, 0)
val inDegree = Array(m) { IntArray(n) }
for (i in 0 until m) {
for (j in 0 until n) {
for (d in 0 until 4) {
val ni = i + dirs[d]
val nj = j + dirs[d + 1]
if (ni in 0 until m && nj in 0 until n && matrix[ni][nj] > matrix[i][j]) {
inDegree[ni][nj]++
}
}
}
}
val queue = ArrayDeque<Pair<Int, Int>>()
for (i in 0 until m) {
for (j in 0 until n) {
if (inDegree[i][j] == 0) queue.add(i to j)
}
}
var layers = 0
while (queue.isNotEmpty()) {
layers++
repeat(queue.size) {
val (x, y) = queue.removeFirst()
for (d in 0 until 4) {
val nx = x + dirs[d]
val ny = y + dirs[d + 1]
if (nx in 0 until m && ny in 0 until n && matrix[nx][ny] > matrix[x][y]) {
if (--inDegree[nx][ny] == 0) {
queue.add(nx to ny)
}
}
}
}
}
return layers
}
}🔑 Takeaways
- Pattern: 矩陣上的 DAG 最長路徑 — DFS + Memoization 或拓撲排序
- Key trick: 嚴格遞增保證無環，可以直接用記憶化搜尋；拓撲排序的層數即為最長路徑