最小体力消耗路径
题目表述
你准备参加一场远足活动。给你一个二维 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
解法一：并查集
可以把二维表看成是一张无环图，边的节点差值的绝对值是无环图边的权重。
将无环图的边按权重排序，依次加入并查集直到左上角跟右下角连通即可。
时间复杂度：O(mnlog(mn)) 空间复杂度：O(mn)
代码实现
from typing import List
class UnionFind:
"""并查集"""
def __init__(self, n:int):
self.parent = list(range(n))
self.size = [1] * n
def findSet(self, x: int)->int:
"""查找元素的根元素，同时找到后将元素连接到根上"""
if self.parent[x] == x:
return x
self.parent[x] = self.findSet(self.parent[x])
return self.parent[x]
def unite(self, x, y)->bool:
"""将两个集合合并"""
# 已经在同一个集合中，无需合并
if self.parent[x] == self.parent[y]:
return False
# 查找根元素
x = self.findSet(x)
y = self.findSet(y)
# 将较小的树加入较大者（保证查找效率）
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] += self.size[y]
return True
def connected(self, x, y)->bool:
"""两个节点是否连通"""
return self.findSet(x) == self.findSet(y)
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
edges = []
for i in range(m):
for j in range(n):
idx = i * n + j
if i > 0: # 垂直边
edges.append([idx-n, idx, abs(heights[i][j]-heights[i-1][j])])
if j > 0: # 水平边
edges.append([idx-1, idx, abs(heights[i][j]-heights[i][j-1])])
# 将边按照权重排序
edges.sort(key=lambda x:x[2])
# 并查集搜索，只需要找到连通的路径即可
uf = UnionFind(m*n)
res = 0
for x, y, v in edges:
uf.unite(x, y)
if uf.connected(0, m*n-1):
res = v
break
return res
package leetcode
import "sort"
type UnionFind struct {
Parent []int
Size []int
}
// findSet 查找集合根节点
func (uf *UnionFind) findSet(x int) int {
if x == uf.Parent[x] {
return x
}
uf.Parent[x] = uf.findSet(uf.Parent[x])
return uf.Parent[x]
}
// unite 合并集合
func (uf *UnionFind) unite(x, y int) bool {
if uf.Parent[x] == uf.Parent[y] {
return false
}
x = uf.findSet(x)
y = uf.findSet(y)
if uf.Size[x] < uf.Size[y] {
x, y = y, x
}
uf.Parent[y] = x
uf.Size[x] += uf.Size[y]
return true
}
// connected x, y 是否连通
func (uf *UnionFind) connected(x, y int) bool {
return uf.findSet(x) == uf.findSet(y)
}
type Edge struct {
x int
y int
v int
}
func makeRange(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = i
}
return arr
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func minimumEffortPath(heights [][]int) int {
m, n := len(heights), len(heights[0])
edges := []Edge{}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
idx := i*n + j
if i > 0 {
edges = append(edges, Edge{idx - n, idx, abs(heights[i][j] - heights[i-1][j])})
}
if j > 0 {
edges = append(edges, Edge{idx - 1, idx, abs(heights[i][j] - heights[i][j-1])})
}
}
}
sort.Slice(edges, func(i, j int) bool { return edges[i].v < edges[j].v })
uf := UnionFind{makeRange(m * n), makeRange(m * n)}
for _, edge := range edges {
uf.unite(edge.x, edge.y)
if uf.connected(0, m*n-1) {
return edge.v
}
}
return 0
}