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.
public class Solution { PRivate static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int longestIncreasingPath(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int m = matrix.length; int n = matrix[0].length; int[][] cache = new int[m][n]; int max = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { max = Math.max(max, dfs(matrix, i, j, m, n, cache)); } } return max; } public int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache){ if(cache[i][j] != 0) return cache[i][j]; int max = 1; for (int[] dir : dirs) { int x = dir[0] + i; int y = dir[1] + j; if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue; max = Math.max(max, 1+dfs(matrix, x, y, m, n, cache)); } cache[i][j] = max; return max; }}新闻热点
疑难解答
