描述
给定一个矩阵,矩阵内所有数均为非负整数。
求一条路径,该路径上所有数是递增的。
这个路径必须满足以下条件:
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; } }
复杂度:
时间复杂度:, 和 分别是矩阵的行数和列数。拓扑排序的时间复杂度是,其中 是节点数,是边数。在矩阵中,。
空间复杂度:,其中 和分别是矩阵的行数和列数。空间复杂度主要取决于队列的大小,队列中的元素个数不会超过。