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

题目描述

给定一个 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，返回0if (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 数组，我们可以确保每个位置的最长路径只计算一次，从而将时间复杂度降低到线性级别。
这题整体难度一般，和之前的求岛屿数量完全类似。但是仔细想想还是要多多注意，比如它还是要遍历整个数组，因为从任何路径走都是有可能的。另外幸好是单调递增，如果是单调非减的话就麻烦很多，因为单调非减会不停来回震荡，就很麻烦。