给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
1
2
3
4
5
6
7
8
| 输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
|
示例 2:
1
2
3
4
5
6
7
8
| 输入: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
|
将矩阵看成一个有向图，每个元素对应图中一个结点，如果两个相邻元素的值不相等，则存在一条从较小值到较大值的有向边，问题转化为在有向图中寻找最长路径。
从一个结点开始进行深度优先搜索，可以得到从该结点开始的最长递增路径，对矩阵中每个结点进行深度优先搜索后可得到最长递增路径的长度。
朴素深度优先搜索的问题是进行了大量的重复计算，同一个结点会被访问多次，每次都重新计算，由于同一个元素的最长递增路径是不变的，我们可以使用矩阵 memo 来存储已经计算过的结果。
使用记忆化深度优先搜索，当访问到一个元素(i, j)时，如果memo[i][j] != 0，说明该元素的结果已经计算过，直接返回结果；否则需要计算结果，并将其存入 memo 中。
我们维护一个最大值 max，当遍历完矩阵中所有的元素时即可得到结果。
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
41
42
43
| class Solution {
public int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int rows, cols;
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return 0;
}
rows = matrix.length;
cols = matrix[0].length;
int[][] memo = new int[rows][cols];
int ans = 0;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
ans = Math.max(ans, dfs(matrix, i, j, memo));
}
}
return ans;
}
public int dfs(int[][] matrix, int row, int col, int[][] memo){
if(memo[row][col] != 0){
return memo[row][col];
}
++memo[row][col];
for(int[] dir : dirs){
int newRow = row + dir[0], newCol = col + dir[1];
if(newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && matrix[newRow][newCol] > matrix[row][col]){
memo[row][col] = Math.max(memo[row][col], dfs(matrix, newRow, newCol, memo) + 1);
}
}
return memo[row][col];
}
}
|
时间复杂度O(mn)，其中 m 和 n 是矩阵的行数和列数。深度优先搜索的时间复杂度为O(V + E),其中 V 是结点书，E 是边数。在矩阵中 O(V) = O(mn)，O(E) 近似为 O(4mn)。
空间复杂度O(mn)。