解法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];
   }
}