矩阵中的最长递增路径
方法一：DFS+记忆化搜索
将矩阵看成一个有向图，每个单元格对应图中的一个节点，如果相邻的两个单元格的值不相等，则在相邻的两个单元格之间存在一条从较小值指向较大值的有向边。问题转化成在有向图中寻找最长路径。
深度优先搜索是非常直观的方法。从一个单元格开始进行深度优先搜索，即可找到从该单元格开始的最长递增路径。对每个单元格分别进行深度优先搜索之后，即可得到矩阵中的最长递增路径的长度。
但是如果使用朴素深度优先搜索，时间复杂度是指数级，会超出时间限制，因此必须加以优化。
朴素深度优先搜索的时间复杂度过高的原因是进行了大量的重复计算，同一个单元格会被访问多次，每次访问都要重新计算。由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。用矩阵 $memo$ 作为缓存矩阵，已经计算过的单元格的结果存储到缓存矩阵中。
1 | class Solution { |
2 | public int[][] dirs = {{-1,0}, {1,0}, {0,1}, {0,-1}}; |
3 | public int rows; |
4 | public int columns; |
5 | public int longestIncreasingPath(int[][] matrix) { |
6 | if(matrix == null || matrix.length==0 || matrix[0].length==0){ |
7 | return 0; |
8 | } |
9 | rows = matrix.length; |
10 | columns = matrix[0].length; |
11 | int[][] memo = new int[rows][columns]; |
12 | int ans = 0; |
13 | for(int i=0; i<rows; i++){ |
14 | for(int j=0; j<columns; j++){ |
15 | ans = Math.max(ans, dfs(matrix,i,j,memo)); |
16 | } |
17 | } |
18 | return ans; |
19 | } |
20 | public int dfs(int[][]matrix, int row, int column, int[][] memo){ |
21 | if(memo[row][column] != 0){ |
22 | return memo[row][column]; |
23 | } |
24 | memo[row][column]++; |
25 | for(int i=0; i<4; i++){ |
26 | int newrow = row + dirs[i][0]; |
27 | int newcol = column + dirs[i][1]; |
28 | if(newrow>=0 && newrow<rows && newcol>=0 && newcol<columns && matrix[row][column] < matrix[newrow][newcol]){ |
29 | memo[row][column] = Math.max(memo[row][column], dfs(matrix, newrow, newcol, memo)+1); |
30 | } |
31 | } |
32 | return memo[row][column]; |
33 | } |
34 | } |
复杂度分析：
- 时间复杂度：$O(mn)$，其中$m$和$n$分别是矩阵的行数和列数。深度优先搜索的时间复杂度为$O(V+E)$，其中$V$是节点数，$E$是边数。在矩阵中，$O(V)=O(mn)$，$O(E)\approx O(4mn)=O(mn)$。
- 空间复杂度：$O(mn)$。
方法二：动态规划+拓扑排序
我们可以先用动态规划求出每个点的出度$outdegree$，再利用拓扑排序求解，从所有出度为 0 的单元格开始广度优先搜索，每一轮搜索都会遍历当前层的所有单元格，更新其余单元格的出度，并将出度变为 0 的单元格加入下一层搜索。当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度。
对于某个点$(i,j)$的出度，可以由转移方程得到：
$$
outdegree[i][j] = max(outdegree[x][y])+1
$$
其中$(x,y)$是与$(i,j)$相邻的点，且$matrix[i][j]<matrix[x][y]$。
1 | class Solution { |
2 | public int[][] dirs = {{-1,0}, {1,0}, {0,1}, {0,-1}}; |
3 | public int rows; |
4 | public int columns; |
5 | public int longestIncreasingPath(int[][] matrix) { |
6 | if(matrix == null || matrix.length==0 || matrix[0].length==0){ |
7 | return 0; |
8 | } |
9 | rows = matrix.length; |
10 | columns = matrix[0].length; |
11 | int[][] outdegrees = new int[rows][columns]; |
12 | int ans = 0; |
13 | for(int i=0; i<rows; i++){ |
14 | for(int j=0; j<columns; j++){ |
15 | for(int[] dir : dirs){ |
16 | int newrow = i + dir[0]; |
17 | int newcol = j + dir[1]; |
18 | if(newrow>=0 && newrow<rows && newcol>=0 && newcol<columns && matrix[i][j]>matrix[newrow][newcol]){ |
19 | //求各个点的出度 |
20 | outdegrees[newrow][newcol]++; |
21 | } |
22 | } |
23 | } |
24 | } |
25 | Queue<int[]> queue = new LinkedList<int[]>(); |
26 | for(int i=0; i<rows; i++){ |
27 | for(int j=0; j<columns; j++){ |
28 | if(outdegrees[i][j] == 0){ |
29 | queue.offer(new int[]{i,j}); |
30 | } |
31 | } |
32 | } |
33 | while(!queue.isEmpty()){ |
34 | ans++; |
35 | int size = queue.size(); |
36 | //进行层序遍历 |
37 | for(int i=0; i<size; i++){ |
38 | int[] ele = queue.poll(); |
39 | for(int[] dir : dirs){ |
40 | int newrow = ele[0] + dir[0]; |
41 | int newcol = ele[1] + dir[1]; |
42 | if(newrow>=0 && newrow<rows && newcol>=0 && newcol<columns && matrix[ele[0]][ele[1]]>matrix[newrow][newcol]){ |
43 | outdegrees[newrow][newcol]--; |
44 | //将出度为0的点加入队列 |
45 | if(outdegrees[newrow][newcol] == 0){ |
46 | queue.offer(new int[]{newrow, newcol}); |
47 | } |
48 | } |
49 | |
50 | } |
51 | } |
52 | } |
53 | return ans; |
54 | } |
55 | |
56 | } |
复杂度分析：
- 时间复杂度：$O(mn)$，其中$m$和$n$分别是矩阵的行数和列数。深度优先搜索的时间复杂度为$O(V+E)$，其中$V$是节点数，$E$是边数。在矩阵中，$O(V)=O(mn)$，$O(E)\approx O(4mn)=O(mn)$。
- 空间复杂度：$O(mn)$。