剑指OfferII112.最长递增路径

题目

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4

解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：输入：matrix = [[3,4,5],[3,2,6],[2,2,1]] 输出：4

解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：输入：matrix = [[1]] 输出：1

提示：m == matrix.length

n == matrix[i].length

1 <= m, n <= 200

0 <= matrix[i][j] <= 231 - 1

注意：本题与主站 329 题相同：

解题思路分析

1、深度优先搜索；时间复杂度O(n^2),空间复杂度O(n^2)

var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
var n, m int
var arr [][]int

func longestIncreasingPath(matrix [][]int) int {
   n, m = len(matrix), len(matrix[0])
   arr = make([][]int, n)
   for i := 0; i < n; i++ {
      arr[i] = make([]int, m)
   }
   res := 0
   for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
         res = max(res, dfs(matrix, i, j))
      }
   }
   return res
}

func dfs(matrix [][]int, i, j int) int {
   if arr[i][j] != 0 {
      return arr[i][j]
   }
   arr[i][j]++ // 长度为1
   for k := 0; k < 4; k++ {
      x, y := i+dx[k], j+dy[k]
      if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[i][j] {
         arr[i][j] = max(arr[i][j], dfs(matrix, x, y)+1)
      }
   }
   return arr[i][j]
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、广度优先搜索；时间复杂度O(n^2),空间复杂度O(n^2)

var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func longestIncreasingPath(matrix [][]int) int {
   n, m := len(matrix), len(matrix[0])
   arr := make([][]int, n)
   for i := 0; i < n; i++ {
      arr[i] = make([]int, m)
   }
   queue := make([][2]int, 0) // 从最大数开始广度优先搜索
   for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
         for k := 0; k < 4; k++ {
            x, y := i+dx[k], j+dy[k]
            if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[i][j] {
               arr[i][j]++ // 四周大于当前的个数
            }
         }
         if arr[i][j] == 0 { // 四周没有大于当前的数
            queue = append(queue, [2]int{i, j})
         }
      }
   }
   res := 0
   for len(queue) > 0 {
      res++
      length := len(queue)
      for i := 0; i < length; i++ {
         a, b := queue[i][0], queue[i][1]
         for k := 0; k < 4; k++ {
            x, y := a+dx[k], b+dy[k]
            if 0 <= x && x < n && 0 <= y && y < m && matrix[a][b] > matrix[x][y] {
               arr[x][y]--
               if arr[x][y] == 0 { // 个数为0，加入队列
                  queue = append(queue, [2]int{x, y})
               }
            }
         }
      }
      queue = queue[length:]
   }
   return res
}

3、排序+动态规划；时间复杂度O(n^2*log(n)),空间复杂度O(n^2)

var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func longestIncreasingPath(matrix [][]int) int {
   n, m := len(matrix), len(matrix[0])
   dp := make([][]int, n)
   temp := make([][3]int, 0)
   for i := 0; i < n; i++ {
      dp[i] = make([]int, m)
      for j := 0; j < m; j++ {
         dp[i][j] = 1
         temp = append(temp, [3]int{i, j, matrix[i][j]})
      }
   }
   sort.Slice(temp, func(i, j int) bool {
      return temp[i][2] < temp[j][2]
   })
   res := 1 // 一个数的时候，没有周围4个数，此时为1
   for i := 0; i < len(temp); i++ {
      a, b := temp[i][0], temp[i][1]
      for k := 0; k < 4; k++ {
         x, y := a+dx[k], b+dy[k]
         if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[a][b] {
            dp[x][y] = max(dp[x][y], dp[a][b]+1) // 更新长度
            res = max(res, dp[x][y])
         }
      }
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}