最小体力消耗路径

难度: Medium

你准备参加一场远足活动。给你一个二维 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] <= 10⁶

Submission

运行时间: 334 ms

内存: 17.3 MB

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        moves = [[-1,0],[1,0],[0,-1],[0,1]]
        n, m = len(heights), len(heights[0])
        visited = [[False] * m for _ in range(n)]
        dps = [[inf] * m for _ in range(n)]
        dps[n - 1][m - 1] = 0
        heap = [[0,n - 1, m - 1]]
        while heap:
            s,y,x = heappop(heap)
            if visited[y][x]: continue
            visited[y][x] = True
            if y == x == 0: break
            for addY, addX in moves:
                yy, xx = y + addY, x + addX
                if yy < 0 or yy >= n or xx < 0 or xx >= m or visited[yy][xx]: continue
                cs = max(abs(heights[y][x] - heights[yy][xx]), s)
                if dps[yy][xx] <= cs: continue
                dps[yy][xx] = cs
                heappush(heap, [cs,yy, xx])
        return dps[0][0]

Explain

该题解采用的是一个优化的 Dijkstra 算法，通过一个最小堆来维持当前探索的路径中的最大高度差的最小值。首先，定义一个二维数组 `dps` 来存储到每个点的最小体力消耗值，并初始化终点的体力消耗值为0。使用优先队列（最小堆）来按体力消耗递增的顺序处理每个格子。对于当前格子，我们检查它的四个邻居，如果这个邻居没有被访问过，并且通过当前格子到该邻居的路径可以得到更小的体力消耗值，我们就更新邻居的体力消耗值，并将其加入堆中。这个过程重复，直到堆为空，或者我们访问到起点。最终，起点的 `dps` 值就是我们要找的答案。

时间复杂度: O((MN) * log(MN))

空间复杂度: O(MN)

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        moves = [[-1,0],[1,0],[0,-1],[0,1]]  # 定义上下左右四个移动方向
        n, m = len(heights), len(heights[0])  # 地图的行数和列数
        visited = [[False] * m for _ in range(n)]  # 访问标记数组
        dps = [[inf] * m for _ in range(n)]  # 存储到每个节点的最小体力消耗
        dps[n - 1][m - 1] = 0  # 终点的消耗初始化为0
        heap = [[0,n - 1, m - 1]]  # 堆初始化，从终点开始
        while heap:  # 当堆不为空时执行
            s,y,x = heappop(heap)  # 弹出最小消耗的节点
            if visited[y][x]: continue  # 如果该节点已访问，则跳过
            visited[y][x] = True  # 标记当前节点为已访问
            if y == x == 0: break  # 如果到达起点，则结束循环
            for addY, addX in moves:  # 检查四个方向的邻居
                yy, xx = y + addY, x + addX  # 计算邻居的坐标
                if yy < 0 or yy >= n or xx < 0 or xx >= m or visited[yy][xx]: continue  # 如果邻居越界或已访问，则跳过
                cs = max(abs(heights[y][x] - heights[yy][xx]), s)  # 计算到该邻居的体力消耗
                if dps[yy][xx] <= cs: continue  # 如果当前计算的消耗不优于已有的，则跳过
                dps[yy][xx] = cs  # 更新到邻居的最小体力消耗
                heappush(heap, [cs,yy, xx])  # 将邻居加入堆中
        return dps[0][0]  # 返回起点的最小体力消耗

Explore

在优化的Dijkstra算法中，使用最小堆（或优先队列）确保每次从堆中弹出的是具有最小体力消耗值的节点。堆的性质是保证堆顶元素是堆中最小的元素，因此每次从堆中弹出的节点是当前所有待处理节点中体力消耗值最小的。这种结构自然而然地按照体力消耗值的升序来处理节点，从而确保探索过程是贪心地选择最小体力消耗的路径。

在优化的Dijkstra算法中，对于当前节点的每个邻居，算法首先计算从当前节点到该邻居节点通过直接路径的体力消耗值。如果这个新计算的体力消耗值小于邻居节点在dps数组中已存储的体力消耗值，则更新邻居节点的体力消耗值，并将邻居节点加入到堆中以便进一步探索。这样的更新确保了只有当找到一条更优（即体力消耗更小）的路径到达该邻居时，才对其进行更新。

'不优于'在本算法中意味着新计算的体力消耗值不小于在dps数组中已经记录的到那个节点的体力消耗值。换句话说，如果通过当前节点到达其邻居的体力消耗值大于或等于已知到达该邻居的最小体力消耗值，则无需更新，因为这不会改善到达那个邻居的最优路径。

在本题解中，算法从终点开始反向寻找到起点的最小体力消耗路径。这是一种常见的路径搜索优化技术，特别是在目标导向的路径搜索中，从终点开始可以更直接地探索到起点的最优路径。初始化堆时将终点加入是为了从终点开始这一反向搜索，堆中的元素代表当前待处理的节点，其体力消耗值初始化为0，因为从终点到终点的消耗自然是0。这样做有助于简化算法逻辑和实现。