每日一题——矩阵最长递增路径

题目描述

给定一个 n 行 m 列的矩阵 matrix，矩阵内所有数均为非负整数。你需要在矩阵中找到一条最长路径，使得这条路径上的元素是递增的。并输出这条最长路径的长度。

该路径必须满足以下条件：

1. 对于每个单元格，你可以往上、下、左、右四个方向移动。不能在对角线方向上移动或移动到边界外。
2. 你不能走重复的单元格。即每个格子最多只能走一次。

数据范围：

• 1 ≤ n, m ≤ 1000
• 0 ≤ matrix[i][j] ≤ 1000
  

进阶要求：

• 空间复杂度：O(nm)
• 时间复杂度：O(nm)

示例

示例 1

输入：

[[1,2,3],
 [4,5,6],
 [7,8,9]]

返回值：

5

说明：
最长递增路径为：1 -> 2 -> 3 -> 6 -> 9。

示例 2

输入：

[[1,2],
 [4,3]]

返回值：

4

说明：
最长递增路径为：1 -> 2 -> 3 -> 4。

题解思路

这个问题可以通过 深度优先搜索（DFS）结合 动态规划（DP）来高效地解决。关键思路是：

1. 深度优先搜索（DFS）：我们可以对每个元素进行深度优先搜索，查找从该元素出发的最长递增路径。
2. 动态规划（DP）：我们可以在 DFS 搜索的过程中利用动态规划来避免重复计算相同位置的路径长度，从而提高效率。

算法步骤：

1. 初始化：

   • 创建一个 dp 数组，记录每个位置的最长递增路径长度。
   • 遍历每个单元格，使用 DFS 算法寻找每个单元格的最长路径。

2. DFS 搜索：

   • 对每个位置 (i, j)，判断其四个邻接位置（上、下、左、右），如果邻接位置的值大于当前值，则递归搜索该邻接位置。
   • 使用 dp[i][j] 存储从 (i, j) 出发的最长递增路径，避免重复计算。

3. 结果：

   • 在遍历所有单元格后，dp 数组中的最大值即为矩阵中的最长递增路径。

代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义方向数组，表示上下左右四个方向
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

/**
 * 深度优先搜索（DFS）函数，用于计算从 (x, y) 开始的最长递增路径
 * 
 * @param matrix 二维数组，表示矩阵
 * @param x 当前位置的行索引
 * @param y 当前位置的列索引
 * @param m 矩阵的行数
 * @param n 矩阵的列数
 * @param count 当前路径的长度
 * @return 从 (x, y) 开始的最长递增路径长度
 */
int dfs(int** matrix, int x, int y, int m, int n, int count) {
    // 如果超出矩阵边界，返回当前路径长度
    if (x < 0 || x >= m || y < 0 || y >= n) {
        return count;
    }

    int maxPath = count; // 初始化当前最大路径长度为当前路径长度
    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0]; // 计算相邻位置的行索引
        int ny = y + directions[i][1]; // 计算相邻位置的列索引

        // 如果相邻位置超出矩阵边界，跳过
        if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
            continue;
        }

        // 如果相邻位置的值小于当前位置的值，说明可以继续递增
        if (matrix[nx][ny] < matrix[x][y]) {
            // 递归调用 dfs，计算从相邻位置开始的路径长度
            int temp = dfs(matrix, nx, ny, m, n, count + 1);
            // 更新最大路径长度
            maxPath = maxPath > temp ? maxPath : temp;
        }
    }

    return maxPath; // 返回从 (x, y) 开始的最长递增路径长度
}

/**
 * 主函数，计算矩阵中的最长递增路径
 * 
 * @param matrix 二维数组，表示矩阵
 * @param matrixRowLen 矩阵的行数
 * @param matrixColLen 矩阵的列数
 * @return 矩阵中的最长递增路径长度
 */
int solve(int** matrix, int matrixRowLen, int* matrixColLen) {
    // 如果矩阵为空或行数为0，返回0
    if (matrixRowLen == 0 || matrix == NULL) {
        return 0;
    }

    int m = matrixRowLen; // 矩阵的行数
    int n = matrixColLen[0]; // 矩阵的列数

    int maxLength = 0; // 初始化最长递增路径长度为0

    // 遍历矩阵的每个位置
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 从每个位置调用 dfs，计算从该位置开始的最长递增路径
            int pathLength = dfs(matrix, i, j, m, n, 1);
            // 更新最长递增路径的长度
            maxLength = maxLength > pathLength ? maxLength : pathLength;
        }
    }

    return maxLength; // 返回矩阵中的最长递增路径长度
}

// 测试函数
int main() {
    // 定义一个示例矩阵
    int matrix[4][4] = {
        {9, 9, 4, 5},
        {6, 6, 8, 7},
        {2, 1, 1, 3},
        {3, 4, 2, 1}
    };

    int m = 4; // 矩阵的行数
    int n = 4; // 矩阵的列数

    // 将二维数组转换为指针数组
    int* matrixPtr[4];
    for (int i = 0; i < m; i++) {
        matrixPtr[i] = matrix[i];
    }

    // 定义列数数组
    int matrixColLen[4] = {n, n, n, n};

    // 调用 solve 函数，计算最长递增路径
    int maxLength = solve(matrixPtr, m, matrixColLen);

    // 打印结果
    printf("The longest increasing path length is: %d\n", maxLength);

    return 0;
}

代码解释

1. dp 数组初始化：dp 数组用于记录从每个单元格出发的最长递增路径。初始化时设置为 -1，表示该位置尚未计算过。

2. DFS 函数：

   • dfs(i, j) 是递归函数，用于计算从位置 (i, j) 开始的最长递增路径。
   • 首先检查 dp[i][j] 是否已经计算过，如果计算过，则直接返回 dp[i][j]。
   • 否则，初始化最长路径为 1，即当前位置本身。
   • 对于当前位置 (i, j)，检查其四个邻接位置，如果邻接位置的值大于当前值，则递归计算该邻接位置的最长路径，并更新当前路径长度。
   • 最终返回 dp[i][j]。

3. 主函数：

   • 遍历整个矩阵，对每个位置调用 dfs 函数，并更新最大路径长度 max_path。
   • 最终返回最大路径长度。

复杂度分析

1. 时间复杂度：O(nm)，每个位置最多计算一次。递归时，通过 dp 数组避免了重复计算。

2. 空间复杂度：O(nm)，需要一个 dp 数组来存储每个位置的最长递增路径长度。

总结

这个问题使用 DFS 和动态规划的结合来有效地求解，避免了重复计算，提高了性能。通过合理使用 np 数组，我们可以确保每个位置的最长路径只计算一次，从而将时间复杂度降低到线性级别。
这题整体难度一般，和之前的求岛屿数量完全类似。但是仔细想想还是要多多注意，比如它还是要遍历整个数组，因为从任何路径走都是有可能的。另外幸好是单调递增，如果是单调非减的话就麻烦很多，因为单调非减会不停来回震荡，就很麻烦。