329. Longest Increasing Path in a Matrix

[TokenYangForever]

前言

• 最近在LeetCode上做出了第一道难度为hard的题：) 觉得这题中规中矩挺不错的，mark一下

  题目描述

• 给出一个正整数矩阵，找出其中最长的递增路径的长度。只能上下左右移动，不能走对角线，不能环绕重复路线，不能超越边距。

  举例：
  输入:
  nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
  ]
  返回 最长路径为4 路径为：1->2->6->9

  解题思路

• 基本思路分以下几个点：
• 0.依次遍历输入的矩阵(二维数组)，找出每个点作为起点时的最长递归路径长度，然后返回其中的最大值
• 1.使用dfs递归方法去遍历查找各个方向，建立一个表示移动方向的数组，每次dfs查找一个新的节点是遍历这个数组，得出最大值作为这个点为起点的最长路径，保存到dp中
• 2.新建一个二维数组作为dp数组，每次得到一个坐标点为起点的最大长度时存入dp数组相应位置，以后再查找到这个坐标点时直接返回之前保存的值避免重复运算

• 上面可能说的有点乱，大概就是dfs遍历和dp数组结合，难度其实并不算大，但是可以优化的细节还是挺多的，下面代码附有具体注释

  具体代码

  /**
  * @param {number[][]} matrix
  * @return {number}
  */
  var longestIncreasingPath = function(matrix) {
  if (!matrix || matrix.length === 0) {
      return 0
  }
  
  var direct = [[0, -1], [0, 1], [-1, 0], [1, 0]] // 方向数组
  var max = 1 // 全局最大值
  var dp = new Array() // dp二维数组，保存每个点作为起点的最大路径长度
  var width = matrix[0].length
  var deep = matrix.length
  while (deep) { 
      dp.push(new Array(width).fill(0)) // 每个点初始长度为0，dfs遍历到不为0的情况直接返回她的值(因为是之前已经得到了)
      deep--
  }
  deep = matrix.length
  
  var dfs = function (i, j) {
      if (dp[i][j] > 0) return dp[i][j];
      var mx = 1
      for (var k = 0; k < direct.length; k++) {
          var x = i + direct[k][0]
          var y = j + direct[k][1]
          if (x < 0 || x >= deep || y < 0 || y >=width) { // 超过范围跳过
              continue
          }
          if (matrix[x][y] <= matrix[i][j]) {// 不是递增跳过
              continue
          }
          var len = dfs(x, y) + 1
          mx = Math.max(mx, len)
      }
      dp[i][j] = mx
      return mx
  }
  
  for (var i = 0; i < deep; i++) {
      for (var j = 0; j < width; j++) {
          max = Math.max(max, dfs(i, j))
      }
  }
  return max
  };