当前位置：首页 > news >正文

可视化图解算法60：矩阵最长递增路径

news 2025/9/17 22:35:22

牛客网面试笔试 TOP101

1. 题目

描述

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

这个路径必须满足以下条件：

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

数据范围：1≤n,m≤1000，0 ≤matrix [i] [j]≤1000

进阶：空间复杂度 O(nm) ，时间复杂度 O(nm)

例如：当输入为[[1,2,3],[4,5,6],[7,8,9]]时，对应的输出为5，

其中的一条最长递增路径如下图所示：

示例1

输入：

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

返回值：

说明：

1->2->3->6->9即可。当然这种递增路径不是唯一的。

示例2

输入：

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

返回值：

说明：

 1->2->3->4

备注：

矩阵的长和宽均不大于1000，矩阵内每个数不大于1000

2. 解题思路

首先，我们需要明确题目的要求：

对应的思路如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解。

Python版本：https://www.bilibili.com/cheese/play/ep1374920
Java版本：https://www.bilibili.com/cheese/play/ep1368184
Golang版本：https://www.bilibili.com/cheese/play/ep1365130

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 递增路径的最大长度* @param matrix int整型二维数组 描述矩阵的每个数* @return int整型*/
func solve(matrix [][]int) int {// write code heremaxMat = newArray(len(matrix), len(matrix[0]))maxValue := 0 //最长路径for i := 0; i < len(matrix); i++ {for j := 0; j < len(matrix[i]); j++ {//二维数组中的每一个点都可能是最大路径的起始点preMax := dfs(matrix, i, j, -1)maxValue = max(maxValue, preMax)}}return maxValue
}var (// 如果我们已经知道以该点为头的最长递增路径长度，那么在dfs查找时可以直接使用这个长度，而无需再次计算.// 用一个矩阵将已经计算得到的最长递增路径进行存储maxMat [][]int
)// 以坐标(i,j)为起始点的最长路径
func dfs(mat [][]int, i int, j int, pre int) int {//2.递归终止条件：不是递增，直接返回if mat[i][j] <= pre {return 0}//3.剪枝：如果该点已经计算过，直接返回，不用再重新计算if maxMat[i][j] != 0 {return maxMat[i][j]}maxVal := 0// 1. 递归步骤//1.1 向左if i > 0 {//用 mat[i][j] 作为 pre，去比较其左侧的数据perMax := dfs(mat, i-1, j, mat[i][j])maxVal = max(maxVal, perMax)}//1.2 向右if i < len(mat)-1 {//用 mat[i][j] 作为 pre，去比较其右侧的数据perMax := dfs(mat, i+1, j, mat[i][j])maxVal = max(maxVal, perMax)}//1.3 向上if j > 0 {//用 mat[i][j] 作为 pre，去比较其上侧的数据perMax := dfs(mat, i, j-1, mat[i][j])maxVal = max(maxVal, perMax)}//1.4 向下if j < len(mat[i])-1 {//用 mat[i][j] 作为 pre，去比较其下侧的数据perMax := dfs(mat, i, j+1, mat[i][j])maxVal = max(maxVal, perMax)}maxMat[i][j] = maxVal + 1 //最长路径：上下左右最长的路径+1(当前的点)return maxMat[i][j]
}
func max(a, b int) int {if a >= b {return a}return b
}func newArray(row, column int) [][]int {arr := make([][]int, row)for i := 0; i < row; i++ {arr[i] = make([]int, column)}return arr}

具体完整代码你可以参考下面视频的详细讲解。