LEETCODE 329. Longest Increasing Path in a Matrix 解题思路分析

题目大意：

矩阵中的最长递增路径

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=329

解题思路分析：

看到矩阵求路径问题，应下意识想到这是典型的dfs路径搜索类型题目。我们需要以每一个点为顶点开始dfs搜索。对于每一个点，他可以向上下左右四个方向移动，dfs向下一步移动的条件为，下一步在矩阵内部，下一步在当前路径上没有走过（不能绕圈），并且下一步的值要大于当前数值。dfs完所有路径之后，最长递增路径也就一目了然。

实现代码：

// dfs的四个方向
int[][] dirs=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int[][] memo; // 记忆数组
int height,width; // 数组的高和宽
public int longestIncreasingPath(int[][] matrix) {
    // 如果数组为空，返回0
    if(matrix.length==0) return 0;
    // 数组高度
    height=matrix.length;
    // 数组宽度
    width=matrix[0].length;
    // 返回结果
    int res=0;
    // 初始化记忆数组
    memo=new int[height][width];
    // 访问数组
    boolean[][] visited=new boolean[height][width];
    // 循环每一个点
    for(int r=0;r<height;r++){
        for(int c=0;c<width;c++){
            // 以当前点为起点dfs所有路线，找到最长路线
            res=Math.max(res, dfs(matrix,r,c,visited));
        }
    }
    return res;
}

int dfs(int[][] matrix, int r,int c, boolean[][] visited){
    // 如果当前点能找到的最长路径存在于记忆数组，直接返回
    if(memo[r][c]>0) return memo[r][c];
    // 返回结果
    int res=0;
    // 标记当前点在当前线路已被访问
    visited[r][c]=true;
    // 循环四个方向
    for(int[] dir : dirs){
        // 下个点坐标
        int row=dir[0]+r,col=dir[1]+c;
        // 如果下个点在矩阵内并且当前路径没有访问过该点并且当前点小于下一点
        if(row>=0&&col>=0&&row<height&&col<width
           &&!visited[row][col]&&matrix[r][c]<matrix[row][col]){
            // 递归到下一点，查看下一点能走的最长路径
            res=Math.max(res, dfs(matrix,row,col,visited));
        }
    }
    // 当前路径以走完，恢复当前点没被访问过
    visited[r][c]=false;
    // 将当前点能走的最长路径保存至记忆数组
    memo[r][c]=res+1;
    return res+1;
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 45.59% of Java online submissions for Longest Increasing Path in a Matrix.

Memory Usage: 39 MB, less than 100.00% of Java online submissions for Longest Increasing Path in a Matrix.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-329-longest-increasing-path-in-a-matrix-解题思路分析/