当前位置: 面试刷题>> 矩阵中的最长递增路径 (经典算法题500道)


题目描述补充

给定一个整数矩阵 matrix,找出其中最长递增路径的长度。递增路径定义为:从矩阵中的某个位置 (r, c) 可以移动到 (r+1, c)(r-1, c)(r, c+1)(r, c-1)(如果目标位置在矩阵的边界内且值比当前位置的值大)。

示例

输入:

matrix = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

输出:4

解释:最长递增路径为 [1, 2, 6, 9][1, 2, 6, 8]

PHP 代码示例

function longestIncreasingPath($matrix) {
    if (empty($matrix)) return 0;

    $rows = count($matrix);
    $cols = count($matrix[0]);
    $memo = array_fill(0, $rows, array_fill(0, $cols, 0)); // 用于存储已计算的路径长度
    $maxLen = 0;

    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            $maxLen = max($maxLen, dfs($matrix, $i, $j, $memo, $rows, $cols));
        }
    }

    return $maxLen;
}

function dfs($matrix, $row, $col, &$memo, $rows, $cols) {
    if ($memo[$row][$col] > 0) return $memo[$row][$col]; // 如果已经计算过,直接返回结果

    $directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // 右,左,下,上
    $maxLength = 1;

    foreach ($directions as $dir) {
        $newRow = $row + $dir[0];
        $newCol = $col + $dir[1];
        if ($newRow >= 0 && $newRow < $rows && $newCol >= 0 && $newCol < $cols && $matrix[$newRow][$newCol] > $matrix[$row][$col]) {
            $maxLength = max($maxLength, 1 + dfs($matrix, $newRow, $newCol, $memo, $rows, $cols));
        }
    }

    $memo[$row][$col] = $maxLength; // 缓存结果
    return $maxLength;
}

// 示例用法
$matrix = [
    [9,9,4],
    [6,6,8],
    [2,1,1]
];
echo longestIncreasingPath($matrix); // 输出 4

Python 代码示例

def longestIncreasingPath(matrix):
    if not matrix:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    memo = [[0] * cols for _ in range(rows)]
    max_len = 0

    def dfs(r, c):
        if memo[r][c] > 0:
            return memo[r][c]

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        max_length = 1

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                max_length = max(max_length, 1 + dfs(nr, nc))

        memo[r][c] = max_length
        return max_length

    for i in range(rows):
        for j in range(cols):
            max_len = max(max_len, dfs(i, j))

    return max_len

# 示例用法
matrix = [
    [9,9,4],
    [6,6,8],
    [2,1,1]
]
print(longestIncreasingPath(matrix)) # 输出 4

JavaScript 代码示例

function longestIncreasingPath(matrix) {
    if (!matrix.length) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const memo = Array.from({length: rows}, () => Array(cols).fill(0));
    let maxLen = 0;

    function dfs(r, c) {
        if (memo[r][c] > 0) return memo[r][c];

        const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
        let maxLength = 1;

        for (const [dr, dc] of directions) {
            const nr = r + dr;
            const nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                maxLength = Math.max(maxLength, 1 + dfs(nr, nc));
            }
        }

        memo[r][c] = maxLength;
        return maxLength;
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            maxLen = Math.max(maxLen, dfs(i, j));
        }
    }

    return maxLen;
}

// 示例用法
const matrix = [
    [9,9,4],
    [6,6,8],
    [2,1,1]
];
console.log(longestIncreasingPath(matrix)); // 输出 4

码小课网站中有更多关于算法和数据结构的内容分享给大家学习,欢迎访问并深入学习!

推荐面试题