面试问题“给定问题的优化解决方案”

Question

最近我正在接受面试，面试官问了我一个非常有趣的问题。

我们给出了一个“N x M”的整数矩阵，我们可以跳转到严格大于同一行或列中当前数字的任何数字。我们需要找到我们可以访问的最大单元格数量是多少。我们可以从矩阵内的任意点开始。

例子 ：-

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

答案：- 6

解释：- 在这种情况下，我们有多个正确的路径，其中一个路径如下所示。

0 => 1 => 2 => 3 => 7 => 10

我用 Java 编写了针对给定问题的解决方案

时间复杂度：- N * M * (N + M)

空间复杂度：- 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;
}

在这位面试官说解决方案是正确的并要求我在时间复杂度方面进一步优化它之后。这是我做不到的。

有人可以帮我找到这个问题的优化解决方案吗？

当我在寻找优化的解决方案时，面试官给出了“排序”的提示。

如果有人想玩我的代码 http://tpcg.io/_ERHJNY

更多测试用例

[[0, 0, 0], [0, 0, 0], [0, 0, 0]] 在这种情况下输出应为 1。说明：0

[[0, 0, 0], [0, 0, 0], [0, 0, -1]] 在这种情况下输出应为 2。解释：-1 => 0

[[0, 0, 0], [0, 0, 0], [0, 0, 1]] 在这种情况下输出应为 2。解释：0 => 1

Answer 1

这个问题归结为在有向无环图中找到最长路径。该问题的经典算法是，对于拓扑顺序中的每个顶点 v，以 v 结束的最长路径的长度是一加上 v 的前驱路径的最大值。然后返回总体最大值。

通过制作(matrix[i][j], i, j)三元组并对它们进行排序，我们得到了拓扑顺序。然后，技巧是预先聚合行和列最大值，以便我们可以在 O(1) 时间内执行内部循环，而不是 O(m + n)。

在Python中（为了简单起见，假设矩阵元素是成对不同的，但删除这个假设并不困难）：

def longest_path(matrix):
    ending_in_row = [0] * len(matrix)
    ending_in_column = [0] * max(map(len, matrix))
    for value, i, j in sorted(
        (value, i, j) for (i, row) in enumerate(matrix) for (j, value) in enumerate(row)
    ):
        length = max(ending_in_row[i], ending_in_column[j]) + 1
        ending_in_row[i] = max(ending_in_row[i], length)
        ending_in_column[j] = max(ending_in_column[j], length)
    return max(ending_in_row)


print(longest_path([[1, 0, 10], [3, 9, 7], [2, 6, 5]]))