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:
Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9]
.
Example 2:
Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]
. Moving diagonally is not allowed.
---------------------------Solution #1, typical DFS, 没啥好说的
class Solution { public int longestIncreasingPath(int[][] matrix) { if (matrix.length == 0) return 0; int m = matrix.length, n = matrix[0].length; int[][] inter = new int[m][n]; int longest = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { longest = Math.max(longest, dfs(matrix, i, j, inter, Integer.MAX_VALUE)); } } return longest; } private int dfs(int[][] matrix, int row, int col, int[][] inter, int pre) { if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || matrix[row][col] >= pre) return 0; if (inter[row][col] > 0) return inter[row][col]; int longest = dfs(matrix, row + 1, col, inter, matrix[row][col]); longest = Math.max(longest, dfs(matrix, row - 1, col, inter, matrix[row][col])); longest = Math.max(longest, dfs(matrix, row, col + 1, inter, matrix[row][col])); longest = Math.max(longest, dfs(matrix, row, col - 1, inter, matrix[row][col])); inter[row][col] = longest + 1; return longest + 1; } }
Solution #2, iterative。也是典型的BFS。ToDo, 有空可以写一下
找到所有的起点,一起塞进Queue(或List),同时记录步数
No comments:
Post a Comment