矩阵最长递增路径优化方案求助：行/列跳转面试算法题

架构老林

2026-7-27

矩阵最长递增路径问题（同行/同列跳转）

问题描述

给定N×M的整数矩阵，可从任意单元格出发，跳转到同行或同列中严格大于当前数值的单元格，求能访问的最大单元格数量。

示例

输入矩阵：

{1, 0, 10}, 
{3, 9, 7}, 
{2, 6, 5}

输出：6
解释：其中一条有效路径为 0 => 1 => 2 => 3 => 7 => 10

现有解法

已实现Java版本解法，时间复杂度为 O(N * M * (N + M))，空间复杂度为 O(N * M)，代码如下：

static void longestIncreasingPath(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;

    int[][] dp = new int[n][m];
    for (int i = 0; i < n; i++)
        Arrays.fill(dp[i], -1);

    int answer = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int length = findSolution(i, j, n, m, matrix, dp);
            answer = Math.max(answer, length);
        }
    }

    System.out.println("Longest increasing path length: " + answer);
}

static int findSolution(int i, int j, int n, int m, int[][] matrix, int[][] dp) {
    if (dp[i][j] != -1) return dp[i][j];

    int res = 1;
    int cur = matrix[i][j];

    for (int newI = 0; newI < n; newI++) {
        int newValue = matrix[newI][j];
        if (newValue > cur) {
            int newRes = 1 + findSolution(newI, j, n, m, matrix, dp);
            res = Math.max(res, newRes);
        }
    }

    for (int newJ = 0; newJ < m; newJ++) {
        int newValue = matrix[i][newJ];
        if (newValue > cur) {
            int newRes = 1 + findSolution(i, newJ, n, m, matrix, dp);
            res = Math.max(res, newRes);
        }
    }

    return dp[i][j] = res;
}

面试官确认解法正确，但要求进一步优化时间复杂度，并给出了「排序」的提示，本人未能完成优化，现寻求该问题的最优解。