描述
给定一个矩阵，矩阵内所有数均为非负整数。
求一条路径，该路径上所有数是递增的。
这个路径必须满足以下条件：
1、对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
2、你不能走重复的单元格。即每个格子最多只能走一次。
示例
输入：
[[1,2,3],[4,5,6],[7,8,9]]
返回值：
5
说明：
1->2->3->6->9即可。当然这种递增路径不是唯一的。
方法一：记忆化深度优先搜索
把矩阵看成一个有向图，每个单元格对应图中的一个节点，问题转化成在有向图中寻找最长路径。我们自然而然想到用深度优先搜索，从一个点开始进行深度优先搜索，即可找到从该点开始的最长递增路径。对每个点分别进行深度优先搜索之后，即可得到矩阵中的最长递增路径的长度。
然而如果使用简单的深度优先搜索，在递归中，每一个点会被重复访问，大量的重复计算会耗费巨大的时间，复杂度是指数级，超出时间限制，因此必须加以优化。
由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化搜索的方法进行优化。因为从这个点出发的最长路径是一定的，所以用矩阵 记录已访问的结点以及最长路径，当下一次访问到该点时如果
,可以直接返回结果，如果
,则进行搜索，并将计算结果存入visited数组。
遍历完矩阵中的所有单元格之后，即可得到矩阵中的最长递增路径的长度。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 递增路径的最大长度
* @param matrix int整型二维数组 描述矩阵的每个数
* @return int整型
*/
public int[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};
public int solve (int[][] matrix) {
// write code here
int rows=matrix.length,columns=matrix[0].length;
if (matrix == null || rows == 0 || columns== 0) {
return 0;
}
//visited数组不仅标记了元素是否被访问过，而且记录了从该点出发的最长路径长度
int[][]visited=new int[rows][columns];
int max=-1;
for(int i=0;i<rows;i++)
{
for(int j=0;j<columns;j++)
{
if(visited[i][j]==0)
{
max=Math.max(max,dfs(i,j,matrix,visited));
}
}
}
return max;
}
int dfs(int i,int j,int[][]matrix,int[][]visited){
int rows=matrix.length,columns=matrix[0].length;
//边界条件
if(i<0||i>=rows||j<0||j>=columns)
return 0;
//该点的最长路径长度已经被计算过
if(visited[i][j]>0)return visited[i][j];
visited[i][j]++;
//从该点的上下左右搜索
for(int[]dir:dirs)
{
int x=i+dir[0],y=j+dir[1];
if(x>=0&&x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j]){
visited[i][j]=Math.max(visited[i][j],dfs(x,y,matrix,visited)+1);
}
}
return visited[i][j];
}
}复杂度：
时间复杂度：
，
和
分别是矩阵的行数和列数。深度优先搜索的时间复杂度是
，
是节点数，
是边数。在矩阵中，
，
。
空间复杂度：
和
分别是矩阵的行数和列数。空间复杂度主要取决于缓存和递归调用深度，缓存的空间复杂度是
，递归调用深度不会超过
。
方法二：拓扑排序
拓扑排序，对可能存在的每一条有向边，管理点的出度，
当一个点的出度为0时，说明它是当前（注意是当前，不是最终）一条路径的终点。那么可以先将所有出度为0的点入队，将这些出度为0的点视为第一层，每次出队一个，遍历它的邻接点，并修改邻接点的出度，如果有出度为0的点就入队，直到第一层的点出队完，接着出队第二层的点（也就是第一层里新加入的出度为0的点），这样，很明显最长的递增路径长度就是层数。
代码如下
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 递增路径的最大长度
* @param matrix int整型二维数组 描述矩阵的每个数
* @return int整型
*/
public int[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};
public int solve (int[][] matrix) {
// write code here
int rows=matrix.length,columns=matrix[0].length;
if (matrix == null || rows == 0 || columns== 0) {
return 0;
}
//存储各个点的出度
int[][] outdegrees=new int[rows][columns];
int i,j;
for(i=0;i<rows;i++)
{
for(j=0;j<columns;j++)
{
for(int[]dir:dirs)
{
int newRow=i+dir[0],newCol=j+dir[1];
//初始化各个点的出度
if(newRow>=0&&newRow<rows&&newCol>=0&&newCol<columns&&matrix[newRow][newCol]>matrix[i][j]){
outdegrees[i][j]++;
}
}
}
}
Queue<int[]>q=new LinkedList<>();
for(i=0;i<rows;i++){
for(j=0;j<columns;j++){
//将出度为0的结点入队
if(outdegrees[i][j]==0)
{
q.add(new int[]{i,j});
}
}
}
int res=0;
while(!q.isEmpty())
{
res++;
//遍历当前层的所有点
int size=q.size();
for(i=0;i<size;i++){
int[]poll=q.poll();
int row=poll[0],col=poll[1];
for(int[]dir:dirs){
int newRow=row+dir[0],newCol=col+dir[1];
if(newRow>=0&&newRow<rows&&newCol>=0&&newCol<columns&&matrix[newRow][newCol]<matrix[row][col]){
//更新其余点的出度，,并将出度变为0的点加入下一层搜索
if(--outdegrees[newRow][newCol]==0){
q.add(new int[]{newRow,newCol});
}
}
}
}
}
//搜索总层数即为最长路径长度
return res;
}
}复杂度：
时间复杂度：
，其中
。
空间复杂度：
。
京公网安备 11010502036488号