给定一个 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
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
}
Hard题目,思路简单一点采用排序+动态规划方法,也可以采用常规的深度优先搜索和广度优先搜索
页面更新:2024-05-26
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号