題目
329. Longest Increasing Path in a Matrix
題目描述
給定一個整數(shù)矩陣镜悉,找出最長遞增路徑的長度。
對于每個單元格医瘫,你可以往上侣肄,下,左登下,右四個方向移動茫孔。 你不能在對角線方向上移動或移動到邊界外(即不允許環(huán)繞)叮喳。
示例 1:
輸入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
輸出: 4
解釋: 最長遞增路徑為 [1, 2, 6, 9]被芳。
示例 2:
輸入: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
輸出: 4
解釋: 最長遞增路徑是 [3, 4, 5, 6]。注意不允許在對角線方向上移動馍悟。
題解
題目意思是查找最長遞增路徑畔濒,簡單點就是直接對每個點深搜能成型的遞增路徑然后比較一下,但是這樣會直接超時锣咒, 然后我做了一個剪枝因為是最長遞增路徑侵状,所以對每個點都有一條最長的邊赞弥,我們只要保存每個已搜點的最長長度,然后在之后搜索到改點的時候直接返回改點的最長長度趣兄。
代碼
int max;
int[][] mappp;
public int longestIncreasingPath(int[][] matrix) {
max = 0;
if (matrix.length == 0)
return 0;
mappp = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (mappp[i][j] == 0) {
max = Math.max(max, dfs(i, j, 1, matrix, -1));
}
}
}
return max;
}
public int dfs(int i, int j, int length, int[][] map, int num) {
if (i >= 0 && i < map.length && j >= 0 && j < map[0].length && map[i][j] > num) {
if (mappp[i][j] != 0)
return mappp[i][j] + length;
int maxx = 0;
int a = dfs(i - 1, j, length + 1, map, map[i][j]);
int b = dfs(i + 1, j, length + 1, map, map[i][j]);
int c = dfs(i, j - 1, length + 1, map, map[i][j]);
int d = dfs(i, j + 1, length + 1, map, map[i][j]);
maxx = Math.max(a, Math.max(b, Math.max(c, d)));
mappp[i][j] = maxx - length;
return maxx;
}
return length - 1;
}
提交結(jié)果
image.png