首页>itarticle>[leetcode] problem 329 – longest increasing path in a matrix
[leetcode] problem 329 – longest increasing path in a matrix
admin11月 13, 20200
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
No.1
Input: nums =
1 2 3 4 5
[ [9,9,4], [6,6,8], [2,1,1] ]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
No.2
Input: nums =
1 2 3 4 5
[ [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.
publicint(int[][] matrix){ int result = 0; if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result; int m = matrix.length; int n = matrix[0].length; int[][] path = newint[m][n];
for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) result = Math.max(result, dfs(matrix, path, m, n, i, j)); }
return result; }
privateintdfs(int[][] matrix, int[][] path, int m, int n, int x, int y){ if (path[x][y] != 0) return path[x][y];
path[x][y] = 1; for (int[] dir : dirs) { int newX = x + dir[0]; int newY = y + dir[1];
if (newX < 0 || newY < 0 || newX >= m || newY >= n) continue; if (matrix[x][y] >= matrix[newX][newY]) continue; path[x][y] = Math.max(path[x][y], 1 + dfs(matrix, path, m, n, newX, newY)); }
近期评论