LeetCode329. Longest Increasing

1、题目链接

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

2、解题思路

题目意思是说给你一个二维数组，数组中都是一些数组，让你找出最长且递增的一条路径，需要注意的是，数组中的每个元素，你只能从其上下左右进行选择，不能对角线选择；那怎么找呢，我的想法是遍历整个数组，然后通过判断某个节点的上下左右节点是否大于该节点来进行深度优先搜索（递归搜索），按照往常的思路，我们还需要定义一个标志位来判断某个节点是否访问过，这样达到一个优化的作用。

3、代码

public int longestIncreasingPath(int[][] matrix) {
    int max = 0;
    int rLength = matrix.length;
    if (rLength == 0) {
        return 0;
    }
    int cLength = matrix[0].length;
    int[][] visited = new int[rLength][cLength];
    for (int i = 0; i < rLength; i++) {
        for (int j = 0; j < cLength; j++) {
            max = Math.max(max, dfs(i, j, matrix, visited));
        }
    }
    return max;
}
public int dfs(int i, int j, int[][] matrix, int[][] visited) {
    if (visited[i][j] != 0) return visited[i][j];
    visited[i][j] = 1;
    if (i >= 0 && i < matrix.length && j >= 0 && j+1 < matrix[0].length && matrix[i][j] < matrix[i][j + 1]) {
        visited[i][j] = Math.max(visited[i][j], dfs(i, j + 1, matrix, visited) + 1);
    }
    if (i >= 0 && i < matrix.length && j >= 1 && j < matrix[0].length && matrix[i][j] < matrix[i][j - 1]) {
        visited[i][j] = Math.max(visited[i][j], dfs(i, j - 1, matrix, visited) + 1);
    }
    if (i >= 0 && i+1 < matrix.length && j >= 0 && j < matrix[0].length && matrix[i][j] < matrix[i + 1][j]) {
        visited[i][j] = Math.max(visited[i][j], dfs(i + 1, j, matrix, visited) + 1);
    }
    if (i >= 1 && i < matrix.length && j >= 0 && j < matrix[0].length && matrix[i][j] < matrix[i - 1][j]) {
        visited[i][j] = Math.max(visited[i][j], dfs(i - 1, j, matrix, visited) + 1);
    }
    return visited[i][j];
}

4、结果