329. Longest Increasing Path in a Matrix

Hard

Description

給定一個 m x n 的整數矩陣，找出最長遞增路徑的長度。每一步可以往上下左右四個方向移動，但下一格的值必須嚴格大於當前格。

Example:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4 (路徑: 1 -> 2 -> 6 -> 9)

Intuition#

從每個格子出發做 DFS，用記憶化避免重複計算；因為路徑嚴格遞增，不會有環。

從每個格子出發找最長遞增路徑，取所有起點的最大值
因為值嚴格遞增，所以不可能回頭，天然無環，適合記憶化搜尋
memo[i][j] 記錄從 (i,j) 出發的最長遞增路徑長度

Approaches#

1: DFS + Memoization#

概念: 從每個格子出發做 DFS，用 memo 陣列快取結果，若 memo 已有值則直接回傳。
時間複雜度: O(m * n)，每個格子最多計算一次
空間複雜度: 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: 拓撲排序（BFS）#

概念: 將矩陣看成 DAG，從「沒有更小鄰居的格子」（入度為 0）開始 BFS，逐層剝離，層數就是最長路徑。
時間複雜度: O(m * n)
空間複雜度: 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 或拓撲排序
關鍵技巧: 嚴格遞增保證無環，可以直接用記憶化搜尋；拓撲排序的層數即為最長路徑