NC138：矩阵最长递增路径

解法1：记忆化+深度优先

链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/javashi-xian-shen-du-you-xian-chao-ji-jian-dan-yi-/
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
---先从一个格子开始找，对比它4周的格子，有没有比它小的，如果有，比如有A，B，C三个格子都比它小，那么当前格子的最大连续递增长度就是这3个格子的最大连续递增长度中的最大值+1（有点绕，多读两遍应该就可以理解了），那么A，B，C的最大长度从哪里来呢，答案肯定是递归去找，直到找到一个比它四周都小的格子，当前格子长度就定为1，至此，整个思路就缕清了，需要用一个与matrix一样大小的数组来存放每一个格子的最大递增长度

• 时间复杂度：O(mn) 需要将整个数组遍历一遍，由于有visited记录，不会重复遍历

• 空间复杂度：O(mn) 需要一个与matrix同样大小的数组，记录已经访问过的格子

  class Solution {
    public int solve(int[][] matrix) {
        if(matrix.length == 0){
            return 0;
        }
        //visited有两个作用：1.判断是否访问过，2.存储当前格子的最长递增长度
        int[][] visited = new int[matrix.length][matrix[0].length];
        int max = 0;
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                if(visited[i][j] == 0){
                    //这里先做一次比较找出max，可以避免最后再去遍历一个visited数组
                    max = Math.max(max, dfs(i, j, matrix, visited));
                }
                //max = Math.max(max, visited[i][j]);
  
            }
        }
        return max;
    }
    public int dfs(int i, int j, int[][] matrix, int[][] visited){
        if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length){
            return 0;
        }
        if(visited[i][j] > 0){
            return visited[i][j];
        }
        int max = 0;
        //这里分别去判断4周是否比当前数小，然后去递归遍历
        if(i - 1 >= 0 && matrix[i-1][j] < matrix[i][j]){
            max = Math.max(max, dfs(i-1, j, matrix, visited));
        }
        if(i + 1 < matrix.length && matrix[i+1][j] < matrix[i][j]){
            max = Math.max(max, dfs(i+1, j, matrix, visited));
        }
        if(j - 1 >= 0 && matrix[i][j-1] < matrix[i][j]){
            max = Math.max(max, dfs(i, j-1, matrix, visited));
        }
        if(j + 1 < matrix[0].length && matrix[i][j+1] < matrix[i][j]){
            max = Math.max(max, dfs(i, j+1, matrix, visited));
        }
  
        visited[i][j] = max+1;
        return max+1;
  
    }
  }

  解法2：拓扑排序+深度优先

• 链接：https://blog.nowcoder.net/n/df0cf9a6a19a4222b0c6f0cea8db9a3d*

  import java.util.*;
  public class Solution {
     /**
      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
      * 递增路径的最大长度
      * @param matrix int整型二维数组 描述矩阵的每个数
      * @return int整型
      */
     int[][] dp;
     int[] dirs = new int[]{0,1,0,-1,0};
     int m, n;
     public int solve (int[][] matrix) {
         // write code here
         int max = 1;
         m = matrix.length;
         n = matrix[0].length;
         dp = new int[m][n];
         for(int i = 0; i < m; i++) {
             for(int j = 0; j < n; j++) {
                 max = Math.max(max,  dfs(matrix, i, j));
             }
         }
         return max;
     }
  
     private int dfs(int[][] matrix, int x, int y) {
         if(dp[x][y] != 0) {
             return dp[x][y];
         }
  
         dp[x][y] = 1;
         for(int k = 0; k < 4; k++) {
             int nx = x + dirs[k];
             int ny = y + dirs[k+1];
             if(nx>=0 && nx<m && ny>=0 && ny<n && matrix[nx][ny] < matrix[x][y]) {
                 dp[x][y] = Math.max(dp[x][y], 1+dfs(matrix, nx, ny));
             }
         }
         return dp[x][y];
     }
  }