矩阵最长递增路径问题
- 题目描述
- 数据范围：
- 进阶要求：
- 示例
- 示例 1
- 示例 2
- 题解思路
- 算法步骤：
- 代码实现
- 代码解释
- 复杂度分析
- 总结
题目描述
给定一个 n 行 m 列的矩阵 matrix，矩阵内所有数均为非负整数。你需要在矩阵中找到一条最长路径，使得这条路径上的元素是递增的。并输出这条最长路径的长度。
该路径必须满足以下条件：
- 对于每个单元格，你可以往上、下、左、右四个方向移动。不能在对角线方向上移动或移动到边界外。
- 你不能走重复的单元格。即每个格子最多只能走一次。
数据范围：
1 ≤ n, m ≤ 10000 ≤ 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）来高效地解决。关键思路是：
- 深度优先搜索（DFS）：我们可以对每个元素进行深度优先搜索，查找从该元素出发的最长递增路径。
- 动态规划（DP）：我们可以在 DFS 搜索的过程中利用动态规划来避免重复计算相同位置的路径长度，从而提高效率。
算法步骤：
-
初始化：
- 创建一个
dp数组，记录每个位置的最长递增路径长度。 - 遍历每个单元格，使用 DFS 算法寻找每个单元格的最长路径。
- 创建一个
-
DFS 搜索：
- 对每个位置
(i, j)，判断其四个邻接位置（上、下、左、右），如果邻接位置的值大于当前值，则递归搜索该邻接位置。 - 使用
dp[i][j]存储从(i, j)出发的最长递增路径，避免重复计算。
- 对每个位置
-
结果：
- 在遍历所有单元格后，
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;
}
代码解释
-
dp数组初始化：dp数组用于记录从每个单元格出发的最长递增路径。初始化时设置为-1，表示该位置尚未计算过。 -
DFS 函数：
dfs(i, j)是递归函数，用于计算从位置(i, j)开始的最长递增路径。- 首先检查
dp[i][j]是否已经计算过，如果计算过，则直接返回dp[i][j]。 - 否则，初始化最长路径为
1，即当前位置本身。 - 对于当前位置
(i, j)，检查其四个邻接位置，如果邻接位置的值大于当前值，则递归计算该邻接位置的最长路径，并更新当前路径长度。 - 最终返回
dp[i][j]。
-
主函数：
- 遍历整个矩阵，对每个位置调用
dfs函数，并更新最大路径长度max_path。 - 最终返回最大路径长度。
- 遍历整个矩阵，对每个位置调用
复杂度分析
-
时间复杂度：
O(nm)，每个位置最多计算一次。递归时，通过dp数组避免了重复计算。 -
空间复杂度：
O(nm)，需要一个dp数组来存储每个位置的最长递增路径长度。
总结
这个问题使用 DFS 和动态规划的结合来有效地求解，避免了重复计算，提高了性能。通过合理使用 np 数组，我们可以确保每个位置的最长路径只计算一次，从而将时间复杂度降低到线性级别。
这题整体难度一般，和之前的求岛屿数量完全类似。但是仔细想想还是要多多注意，比如它还是要遍历整个数组，因为从任何路径走都是有可能的。另外幸好是单调递增，如果是单调非减的话就麻烦很多，因为单调非减会不停来回震荡，就很麻烦。
