Longest Increasing Path in a Matrix
程序员文章站
2022-07-10 09:18:26
...
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.
我们采用DFS+memory的方法,就是在DFS的同时,记录当前元素所能构成的最大长度,如果下次再访问到这个点的时候直接返回这个点在memory中的值就可以了。时间复杂度为O(m*n),空间复杂度也是O(m*n)。代码如下:
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.
我们采用DFS+memory的方法,就是在DFS的同时,记录当前元素所能构成的最大长度,如果下次再访问到这个点的时候直接返回这个点在memory中的值就可以了。时间复杂度为O(m*n),空间复杂度也是O(m*n)。代码如下:
public class Solution { public int longestIncreasingPath(int[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int[][] memory = new int[matrix.length][matrix[0].length]; int max = 1; for(int i = 0; i < matrix.length; i++) { for(int j = 0; j < matrix[0].length; j++) { max = Math.max(max, getLength(i, j, Integer.MIN_VALUE, memory, matrix)); } } return max; } public int getLength(int i, int j, int min, int[][] memory, int[][] matrix) { if(i < 0 || j < 0 || i == matrix.length || j == matrix[0].length || matrix[i][j] <= min) return 0; if(memory[i][j] != 0) return memory[i][j]; min = matrix[i][j]; int a = getLength(i - 1, j, min, memory, matrix) + 1; int b = getLength(i + 1, j, min, memory, matrix) + 1; int c = getLength(i, j + 1, min, memory, matrix) + 1; int d = getLength(i, j - 1, min, memory, matrix) + 1; memory[i][j] = Math.max(a, Math.max(b, Math.max(c, d))); return memory[i][j]; } }
推荐阅读
-
最长上升子序列(LIS: Longest Increasing Subsequence)
-
The Xor-longest Path(trie树)
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
[LeetCode] Unique Paths && Unique Paths II && Minimum Path Sum (动态规划之 Matrix DP )
-
Longest Increasing Path in a Matrix
-
最长递增子序列(Longest Increasing Subsequence)
-
最长上升子序列(LIS: Longest Increasing Subsequence)
-
Poj3764---The xor-longest Path
-
Longest Absolute File Path
-
388. Longest Absolute File Path