描述
给定一个矩阵,矩阵内所有数均为非负整数。
求一条路径,该路径上所有数是递增的。
这个路径必须满足以下条件:
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;  
    }
}

复杂度:

  • 时间复杂度: 分别是矩阵的行数和列数。拓扑排序的时间复杂度是,其中 是节点数,是边数。在矩阵中,

  • 空间复杂度:,其中 分别是矩阵的行数和列数。空间复杂度主要取决于队列的大小,队列中的元素个数不会超过