深度遍历-求矩阵最长递增路径

一、问题描述

二、解题思路

        和深度遍历-求岛屿数量的思路一致，不过这里不需要设置判断是否产生访问过的boolean二维数组了，因为在这个题目里面是求递增序列，下一个元素只有比当前元素大才会往前走，即使在回头检查时，发现“下一个元素”比当前元素小，直接返回。

深度遍历-求“岛屿数量”-CSDN博客文章浏览阅读200次。java刷题：深度遍历二维数组，解决求不同“岛屿数量”问题。https://blog.csdn.net/hehe_soft_engineer/article/details/139628257?spm=1001.2014.3001.5501

        这里还是要强调一下边界问题，在深度遍历的时候，上下左右移动的边界一定要写清楚。

三、代码实现

import java.util.*;

public class Solution {
    int resMaxLen=0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // 本题目参考岛屿数量，使用深度遍历二维数组方式来寻找最长路径
        int rowSize=matrix.length;
        int colSize=matrix[0].length;
        for(int rowidx=0;rowidx<rowSize;rowidx++){
            for(int colidx=0;colidx<colSize;colidx++){
                dfsFindLess(matrix,rowidx,colidx,-1,0);
            }
        }
        return resMaxLen;
    }

    public void dfsFindLess(int[][] matrix,int row,int col,int preElem,int maxLen){
        //和岛屿数量区别的地方在于，这里不需要设置一个未访问数组来标识是不是回头
        //因为下一个元素只有比当前元素大才会往前走
        if(matrix[row][col]<=preElem){
            return;
        }else{
            maxLen++;
            resMaxLen=Math.max(resMaxLen,maxLen);
            if(row+1<matrix.length){//向下
                dfsFindLess(matrix,row+1,col,matrix[row][col],maxLen);
            }
            if(row-1>=0){//向上
                dfsFindLess(matrix,row-1,col,matrix[row][col],maxLen);
            }
            if(col+1<matrix[0].length){//向右
                dfsFindLess(matrix,row,col+1,matrix[row][col],maxLen);
            }
            if(col-1>=0){//向左
                dfsFindLess(matrix,row,col-1,matrix[row][col],maxLen);
            }
        }
    }
}

四、刷题链接

矩阵最长递增路径_牛客题霸_牛客网