1631. 最小体力消耗路径

Difficulty
Medium
Tags
并查集
BFS
URL
https://leetcode.cn/problems/path-with-minimum-effort/
Star
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
示例 1：
notion imagenotion image
输入：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
通过次数34,319提交次数68,228

分析

本题采用 dfs 暴力求解，遍历每一条路径肯定没问题的，但是这样时间复杂度爆炸。
是否可以采用记忆化搜索呢？答案是不行！ 因为 记忆化搜索 其实和 动态规划 思路的一样的，他不关注 具体的路径， 只关注起点终点，但是本题，显然要关注路径。
我们可以将本题抽象成如下的一个图论模型：
  • 我们将地图中的每一个格子看成图中的一个节点；
  • 我么将两个相邻（左右相邻或者上下相邻）的两个格子对应的节点之间连接一条无向边，边的权值为这两个格子的高度差的绝对值；
  • 我们需要找到一条从左上角到右下角的最短路径，其中一条路径的长度定义为其经过的所有边权的最大值。

并查集

思路
将这 mn 个节点放入并查集中，实时维护它们的连通性。
由于我们需要找到从左上角到右下角的最短路径，因此我们可以将图中的所有边按照权值从小到大进行排序，并依次加入并查集中。当我们加入一条权值为 x 的边之后，如果左上角和右下角从非连通状态变为连通状态，那么 x 即为答案。
题解
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.size = [0 for _ in range(n)]

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])

        return self.root[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.size[root_x] < self.size[root_y]:
                self.root[root_x] = root_y
                self.size[root_y] += self.size[root_x]
            else:
                self.root[root_y] = root_x
                self.size[root_x] += self.size[root_y]

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        graph = []
        for i in range(0, len(heights)):
            for j in range(0, len(heights[0])):
                if i + 1 < len(heights):
                    s = i * len(heights[0]) + j
                    e = (i+1) * len(heights[0]) + j
                    w = abs(heights[i][j] - heights[i+1][j])
                    graph.append([s, e, w])
                    
                if j + 1 < len(heights[0]):
                    s = i * len(heights[0]) + j
                    e = i * len(heights[0]) + j + 1
                    w = abs(heights[i][j] - heights[i][j+1])
                    graph.append([s, e, w])
                

        graph.sort(key=lambda x : x[2])
        start = 0
        target = len(heights[0]) * len(heights) - 1
        
        uf = UnionFind(len(heights[0]) * len(heights))
        for e in graph:
            uf.union(e[0], e[1])
            if uf.find(start) == uf.find(target):
                return e[2]
        return 0

法2 BFS + 优先队列 = 最短路算法

思路 每次都优先走 当前答案 最小的 节点，用堆来维护 最小。
题解
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        queue = []
        queue.append([0, 0, 0])
        dist = [[float("inf")] * len(heights[0]) for _ in heights]
        dist[0][0] = 0

        while queue:
            cur_res, cur_x, cur_y = heapq.heappop(queue)

            for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                nxt_x = cur_x + d[0]
                nxt_y = cur_y + d[1]
                if nxt_x < 0 or nxt_x >= len(heights) or nxt_y < 0 or nxt_y >= len(heights[0]):
                    continue
                
                nxt_res = max(cur_res, abs(heights[cur_x][cur_y] - heights[nxt_x][nxt_y]))
                if nxt_res < dist[nxt_x][nxt_y]:
                    dist[nxt_x][nxt_y] = nxt_res
                    heapq.heappush(queue, [nxt_res, nxt_x, nxt_y])

        return dist[len(heights)-1][len(heights[0])-1]