LeetCode 1631. 最小体力消耗路径

题目描述
你是一个徒步旅行者，要在一个二维网格地图上从左上角(0,0)走到右下角(rows-1, cols-1)。每个格子有一个海拔高度，当你从一个格子走到相邻的上下左右格子时，会消耗体力，消耗的体力值为两个格子海拔高度的绝对差。

你需要找到一条从起点到终点的路径，使得这条路径上的"最大体力消耗值"最小。也就是说，我们要最小化路径上所有相邻格子间高度差的最大值。

例如：
输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 1→3→5→3→5→2→2 的最大高度差是 |3-5|=2

解题过程

步骤1：理解问题本质
这个问题不是求路径总和最小，而是求路径上"最大的单步消耗"最小。想象我们要背着氧气瓶登山，氧气瓶的容量要能支撑最陡的那段路。

步骤2：暴力解法分析
最直接的方法是找出所有路径，计算每条路径的最大高度差，然后取最小值。但网格可能很大，路径数量是指数级的，不可行。

步骤3：关键观察
我们可以把这个问题转化为：找到最小的阈值d，使得存在一条从起点到终点的路径，路径上所有相邻格子间的高度差都不超过d。

换句话说，对于给定的d，我们只需要判断是否存在一条"高度差始终≤d"的路径。

步骤4：二分搜索 + BFS/DFS
基于步骤3的观察，我们可以：

1. 用二分搜索确定d的范围
2. 对于每个候选的d，用BFS或DFS检查是否存在满足条件的路径

具体实现：

def minimumEffortPath(heights):
    rows, cols = len(heights), len(heights[0])
    
    # 二分搜索的左右边界
    left, right = 0, 10**6
    
    def canReach(max_effort):
        """检查是否存在一条路径，所有步的体力消耗≤max_effort"""
        from collections import deque
        visited = [[False] * cols for _ in range(rows)]
        queue = deque([(0, 0)])
        visited[0][0] = True
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while queue:
            x, y = queue.popleft()
            if x == rows-1 and y == cols-1:
                return True
                
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny]:
                    # 检查高度差是否在允许范围内
                    if abs(heights[nx][ny] - heights[x][y]) <= max_effort:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
        return False
    
    # 二分搜索
    while left < right:
        mid = (left + right) // 2
        if canReach(mid):
            right = mid  # 尝试更小的d
        else:
            left = mid + 1  # 需要更大的d
    
    return left

步骤5：Dijkstra算法方法
我们也可以把这个问题看作最短路径问题的变体：

• 每个格子是一个节点
• 相邻格子间的边权是高度差的绝对值
• 路径的"成本"定义为路径上所有边权的最大值（不是总和）

使用Dijkstra算法，但修改松弛条件：

import heapq

def minimumEffortPath(heights):
    rows, cols = len(heights), len(heights[0])
    
    # 最小堆，存储(当前路径的最大高度差, x, y)
    heap = [(0, 0, 0)]
    # 记录到达每个格子的最小最大高度差
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while heap:
        effort, x, y = heapq.heappop(heap)
        
        # 如果到达终点
        if x == rows-1 and y == cols-1:
            return effort
            
        # 如果当前不是最优解，跳过
        if effort > dist[x][y]:
            continue
            
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols:
                # 计算到邻居的effort
                new_effort = max(effort, abs(heights[nx][ny] - heights[x][y]))
                
                # 如果找到更小的最大高度差
                if new_effort < dist[nx][ny]:
                    dist[nx][ny] = new_effort
                    heapq.heappush(heap, (new_effort, nx, ny))
    
    return dist[rows-1][cols-1]

步骤6：算法对比

• 二分+BFS/DFS：时间复杂度O(rows×cols×log(max_height))，容易理解
• Dijkstra变体：时间复杂度O(rows×cols×log(rows×cols))，通常更快

步骤7：实例验证
以题目例子验证：
heights = [[1,2,2],[3,8,2],[5,3,5]]

二分搜索过程：

• 检查d=3：存在路径 1→2→2→2→3→5，最大差max(|1-2|,|2-2|,|2-2|,|2-3|,|3-5|)=2≤3，通过
• 检查d=1：无法到达终点
• 检查d=2：存在路径，最终确定答案为2

这个问题的核心在于理解我们不是最小化路径总和，而是最小化路径上的最大值。