题解 | #矩阵最长递增路径#

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

复杂度：

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

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