leetCode-329:Longest Increasing Path in a Matrix

问题描述

给定一个只包含整数的矩阵，要求找出矩阵中单调递增路径（某个节点与该节点上下左右节点可以构成一个路径）的最大长度。题目链接：**点我**

样例输入输出

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]

输出：4

解释：路径为：1 -> 2 -> 6 -> 9

输入：matrix = [[1]]

输出：1

问题解法

使用记忆化搜索的方式进行求解，分别对矩阵中每个节点作为起始节点进行递归搜索，在搜索过程中使用数组记录已经搜索过的路径的节点的最大长度，以免重复搜索。代码如下：

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int[][] counts = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                search(matrix, counts, i, j);
            }
        }

        int result = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                result = Math.max(result, counts[i][j]);
            }
        }

        return result;
    }

    private int search(int[][] matrix, int[][] counts, int i, int j) {
        if (counts[i][j] != 0) {
            return counts[i][j];
        }

        int num = matrix[i][j];
        int left = 0;
        if (isMove(matrix, num, i, j - 1)) {
            left = search(matrix, counts, i, j - 1);
        }

        int right = 0;
        if (isMove(matrix, num, i, j + 1)) {
            right = search(matrix, counts, i, j + 1);
        }

        int top = 0;
        if (isMove(matrix, num, i - 1, j)) {
            top = search(matrix, counts, i - 1, j);
        }

        int down = 0;
        if (isMove(matrix, num, i + 1, j)) {
            down = search(matrix, counts, i + 1, j);
        }

        counts[i][j] = Math.max(Math.max(Math.max(left, right), Math.max(top, down)) + 1, counts[i][j]);
        return counts[i][j];
    }

    private boolean isMove(int[][] matrix, int num, int i, int j) {
        return i >=0 && i < matrix.length && j >=0 && j < matrix[0].length && num < matrix[i][j];
    }
}