题目

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，

其中 heights[row][col] 表示格子 (row, col) 的高度。

一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。

你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：输入：heights = [[1,2,2],[3,8,2],[5,3,5]] 输出：2

解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。

这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：输入：heights = [[1,2,3],[3,8,4],[5,3,5]] 输出：1

解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] 输出：0

解释：上图所示路径不需要消耗任何体力。

提示：rows == heights.length

columns == heights[i].length

1 <= rows, columns <= 100

1 <= heights[i][j] <= 106

解题思路分析

1、二分查找+广度优先搜索；时间复杂度O(n^2log(n))，空间复杂度O(n^2)

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

func minimumEffortPath(heights [][]int) int {
   n, m := len(heights), len(heights[0])
   left, right := 0, 1000000
   res := 0
   for left <= right {
      mid := left + (right-left)/2 // 二分枚举最大值
      queue := make([][2]int, 0)
      queue = append(queue, [2]int{0, 0})
      visited := make([][]bool, n)
      for i := 0; i < n; i++ {
         visited[i] = make([]bool, m)
      }
      for len(queue) > 0 {
         a, b := queue[0][0], queue[0][1]
         queue = queue[1:]
         for i := 0; i < 4; i++ {
            x, y := a+dx[i], b+dy[i]
            if 0 <= x && x < n && 0 <= y && y < m &&
               visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= mid {
               queue = append(queue, [2]int{x, y})
               visited[x][y] = true
            }
         }
      }
      if visited[n-1][m-1] == true { // 缩小范围
         res = mid
         right = mid - 1
      } else {
         left = mid + 1
      }
   }
   return res
}

func abs(a int) int {
   if a < 0 {
      return -a
   }
   return a
}

2、并查集；时间复杂度O(n^2log(n))，空间复杂度O(n^2)

func minimumEffortPath(heights [][]int) int {
   n, m := len(heights), len(heights[0])
   arr := make([][3]int, 0) // 相邻格子可以连一条边，高度差绝对值最为边的权值
   for i := 0; i < n; i++ {
      for j := 0; j < m; j++ {
         index := i*m + j // 转化为一维坐标
         if i > 0 {
            value := abs(heights[i][j] - heights[i-1][j])      // 上到下
            arr = append(arr, [3]int{index - m, index, value}) // 之前坐标，当前坐标，绝对值
         }
         if j > 0 {
            value := abs(heights[i][j] - heights[i][j-1])      // 左到右
            arr = append(arr, [3]int{index - 1, index, value}) // 之前坐标，当前坐标，绝对值
         }
      }
   }
   sort.Slice(arr, func(i, j int) bool {
      return arr[i][2] < arr[j][2]
   })
   fa = Init(n * m)
   for i := 0; i < len(arr); i++ { // 从小到大枚举高度差绝对值
      a, b, c := arr[i][0], arr[i][1], arr[i][2]
      union(a, b)
      if query(0, n*m-1) == true {
         return c
      }
   }
   return 0
}

func abs(a int) int {
   if a < 0 {
      return -a
   }
   return a
}

var fa []int

// 初始化
func Init(n int) []int {
   arr := make([]int, n)
   for i := 0; i < n; i++ {
      arr[i] = i
   }
   return arr
}

// 查询
func find(x int) int {
   if fa[x] != x {
      fa[x] = find(fa[x])
   }
   return fa[x]
}

// 合并
func union(i, j int) {
   fa[find(i)] = find(j)
}

func query(i, j int) bool {
   return find(i) == find(j)
}

3、Dijkstra；时间复杂度O(n^2log(n))，空间复杂度O(n^2)

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

func minimumEffortPath(heights [][]int) int {
   n, m := len(heights), len(heights[0])
   arr := make([][]int, n) //  高度差绝对值的最大值
   for i := 0; i < n; i++ {
      arr[i] = make([]int, m)
      for j := 0; j < m; j++ {
         arr[i][j] = math.MaxInt32 // 初始化为最大值
      }
   }
   arr[0][0] = 0
   intHeap := make(IntHeap, 0)
   heap.Init(&intHeap)
   heap.Push(&intHeap, [3]int{0, 0, 0})
   for {
      node := heap.Pop(&intHeap).([3]int)
      a, b, c := node[0], node[1], node[2]
      if a == n-1 && b == m-1 { // 返回结果
         return c
      }
      if arr[a][b] < c { // 大于 高度差绝对值的最大值，跳过
         continue
      }
      for i := 0; i < 4; i++ {
         x, y := a+dx[i], b+dy[i]
         if 0 <= x && x < n && 0 <= y && y < m {
            diff := max(c, abs(heights[x][y]-heights[a][b])) // 更新：去 高度差绝对值的最大值 的较大值
            if diff < arr[x][y] {                            // 更新：加入堆，点会重复，通过更新arr[x][y]来过滤
               arr[x][y] = diff
               heap.Push(&intHeap, [3]int{x, y, diff})
            }
         }
      }
   }
   return 0
}

func abs(a int) int {
   if a < 0 {
      return -a
   }
   return a
}

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

type IntHeap [][3]int

func (h IntHeap) Len() int {
   return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
   return h[i][2] < h[j][2]
}

func (h IntHeap) Swap(i, j int) {
   h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
   *h = append(*h, x.([3]int))
}

func (h *IntHeap) Pop() interface{} {
   value := (*h)[len(*h)-1]
   *h = (*h)[:len(*h)-1]
   return value
}

4、二分查找+广度优先搜索+内置函数；时间复杂度O(n^2log(n))，空间复杂度O(n^2)

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

func minimumEffortPath(heights [][]int) int {
   n, m := len(heights), len(heights[0])
   return sort.Search(1000000, func(target int) bool {
      queue := make([][2]int, 0)
      queue = append(queue, [2]int{0, 0})
      visited := make([][]bool, n)
      for i := 0; i < n; i++ {
         visited[i] = make([]bool, m)
      }
      for len(queue) > 0 {
         a, b := queue[0][0], queue[0][1]
         queue = queue[1:]
         if a == n-1 && b == m-1 {
            return true
         }
         for i := 0; i < 4; i++ {
            x, y := a+dx[i], b+dy[i]
            if 0 <= x && x < n && 0 <= y && y < m &&
               visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= target {
               queue = append(queue, [2]int{x, y})
               visited[x][y] = true
            }
         }
      }
      return false
   })
   return 0
}

func abs(a int) int {
   if a < 0 {
      return -a
   }
   return a
}

总结

Medium题目，多种解法