记录Leetcode上的一道题目，欢迎交流，指正错误。
1. 矩阵中的最长递增路径
LeetCode链接
题目：
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 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]。注意不允许在对角线方向上移动。
解题思路：
最基本思路就是遍历matrix中的每一个元素，然后以该元素出发，往上、下、左、右四个方向移动，并统计出最长路径的长度，最后返回所有元素中最长的路径长度。如果这样操作的话，对于同一个元素可能会多次访问，时长会太长，因此通过一个max数组来剪枝。
max数组用来保存以 i , j 出发能拿到的最长路径数，对于max[i][j]不为0的元素表示已经统计过，不需要再次访问，即剪枝。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
int[][] max; // 保存以 i , j 出发能拿到的最大路径数
int row, col; // matrix的行和列
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; // 方向数组
// 返回matrix中最长递增路径
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || (row = matrix.length) == 0 || (col = matrix[0].length) == 0) return 0;
int res = 0;
max = new int[row][col];
for(int i = 0; i < row; i++){
for (int j = 0; j < col; j++) {
if(max[i][j] == 0)
res = Math.max(DFS(matrix, i, j), res);
}
}
return res;
}
//返回以curRow, curCol出发(包含)能拿到的最大路径数
private int DFS(int[][] matrix, int curRow, int curCol) {
if(max[curRow][curCol] != 0)
return max[curRow][curCol];
max[curRow][curCol] = 1;
for (int[] dir : dirs) {
int nextRow = curRow + dir[0];
int nextCol = curCol + dir[1];
if(isRange(nextRow,nextCol) && matrix[nextRow][nextCol] > matrix[curRow][curCol]){
max[curRow][curCol] = Math.max(max[curRow][curCol], DFS(matrix, nextRow, nextCol) + 1);
}
}
return max[curRow][curCol];
}
//校验curRow, curCol是否在matrix边界内
private boolean isRange(int curRow, int curCol) {
return curRow >= 0 && curCol >= 0 && curRow < row && curCol < col;
}
}
|
2. 小结
这是对DFS方法很好的运用。