[Leetcode][第329题][JAVA][矩阵中的最长递增路径][DFS][拓扑排序]

川长思鸟来 2023-03-01 12:56 35阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 记忆化深度优先搜索 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

**复杂度**  
![在这里插入图片描述][20200726141131335.png]

###### 2. 拓扑排序 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

**复杂度**  
![在这里插入图片描述][2020072614124013.png]

class Solution { 
        public int[][] dirs = { { -1, 0}, { 1, 0}, { 0, -1}, { 0, 1}};
        public int rows, columns;
    
        public int longestIncreasingPath(int[][] matrix) { 
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 
                return 0;
            }
            rows = matrix.length;
            columns = matrix[0].length;
            int[][] outdegrees = new int[rows][columns];
            //初始化度 度递增
            for (int i = 0; i < rows; ++i) { 
                for (int j = 0; j < columns; ++j) { 
                    for (int[] dir : dirs) { 
                        int newRow = i + dir[0], newColumn = j + dir[1];
                        if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[i][j]) { 
                            ++outdegrees[i][j];
                        }
                    }
                }
            }
            //边界条件入度 相关点进行递减
            Queue<int[]> queue = new LinkedList<int[]>();
            for (int i = 0; i < rows; ++i) { 
                for (int j = 0; j < columns; ++j) { 
                    if (outdegrees[i][j] == 0) { 
                        queue.offer(new int[]{ i, j});
                    }
                }
            }
            int ans = 0;
            while (!queue.isEmpty()) { 
                ++ans;
                int size = queue.size();
                for (int i = 0; i < size; ++i) { 
                    int[] cell = queue.poll();
                    int row = cell[0], column = cell[1];
                    for (int[] dir : dirs) { 
                        int newRow = row + dir[0], newColumn = column + dir[1];
                        if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column]) { 
                            --outdegrees[newRow][newColumn];
                            if (outdegrees[newRow][newColumn] == 0) { 
                                queue.offer(new int[]{ newRow, newColumn});
                            }
                        }
                    }
                }
            }
            return ans;
        }
    }

#### 【总结】 ####

###### 1. 拓扑排序模板 ######

定边界 - 入队 - 出队 层数即为答案

###### 2.dfs 记忆化搜索 避免超时 ######

转载链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/ju-zhen-zhong-de-zui-chang-di-zeng-lu-jing-by-le-2/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/fd4c90d0f5454c859a163fbbf2b5891d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230208/fab7f0e7fd5e4e7d9c9ef84ed3781a90.png
[20200726141131335.png]: /images/20230208/0ce2a9ab21134c67b36129c5047ffbe9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230208/9d27434e41a84467b9b194200a0d966f.png
[2020072614124013.png]: /images/20230208/a85b7393b8e64140ad863de01238d66e.png