首页 > itarticle > longest increasing path in a matrix

longest increasing path in a matrix

admin 11月 11, 2020 0

Problem:

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

分析：

典型深搜，能够优化的地方在于需要用memo技巧来标记已经走过的路径的最长路径值。

public class  {
    public int longestIncreasingPath(int[][] matrix) {
        int ret = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int[][] memo = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                ret = Math.max(ret, helper(matrix, memo, i, j));
            }
        }
        return ret;
    }
    
    private int helper(int[][] matrix, int[][] memo, int x, int y) {
    
        if (memo[x][y] > 0) return memo[x][y];
        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) return 0;
        int ret = 1;
        int left = 0, right = 0, up = 0, down = 0;
        if (x - 1 >= 0 && matrix[x][y] > matrix[x-1][y])
            left = helper(matrix, memo, x - 1, y);
        if (x + 1 < matrix.length && matrix[x][y] > matrix[x+1][y])
            right = helper(matrix, memo, x + 1, y);
        if (y - 1 >= 0 && matrix[x][y] > matrix[x][y - 1])
            up = helper(matrix, memo, x, y - 1);
        if (y + 1 < matrix[0].length && matrix[x][y] > matrix[x][y+1])
            down = helper(matrix, memo, x, y + 1);
        ret += Math.max(Math.max(left, right), Math.max(up, down));
        memo[x][y] = ret;
        return ret;
    }
}