Medium

题目描述

你是一名徒步旅行者，正在准备即将到来的徒步旅行。给你一个 heights 数组，大小为 rows x columns，其中 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^6

解题思路

这道题可以用多种方法求解：

方法一：Dijkstra算法（推荐） 将二维网格看作图，每个格子是节点，相邻格子间的边权重是高度差的绝对值。我们要找的是从起点到终点的最小最大边权路径。使用优先队列实现的Dijkstra算法，每次选择当前最小体力消耗的路径进行扩展。

方法二：二分查找 + BFS/DFS 二分查找答案，对于每个候选值k，判断是否存在一条路径使得所有相邻格子的高度差都不超过k。通过BFS或DFS验证路径是否存在。

方法三：并查集 + 贪心 将所有边按权重排序，从小到大加入边，直到起点和终点连通。

Dijkstra算法在这种场景下最直观且效率较高，时间复杂度合理。我们维护每个点到起点的最小体力消耗，使用优先队列确保每次处理体力消耗最小的状态。

代码实现

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        
        dist[0][0] = 0;
        pq.push({0, 0, 0});
        
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (!pq.empty()) {
            auto [effort, x, y] = pq.top();
            pq.pop();
            
            if (x == m - 1 && y == n - 1) {
                return effort;
            }
            
            if (effort > dist[x][y]) {
                continue;
            }
            
            for (auto& dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newEffort = max(effort, abs(heights[nx][ny] - heights[x][y]));
                    if (newEffort < dist[nx][ny]) {
                        dist[nx][ny] = newEffort;
                        pq.push({newEffort, nx, ny});
                    }
                }
            }
        }
        
        return 0;
    }
};

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        import heapq
        
        m, n = len(heights), len(heights[0])
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        pq = [(0, 0, 0)]  # (effort, x, y)
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while pq:
            effort, x, y = heapq.heappop(pq)
            
            if x == m - 1 and y == n - 1:
                return effort
                
            if effort > dist[x][y]:
                continue
                
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    new_effort = max(effort, abs(heights[nx][ny] - heights[x][y]))
                    if new_effort < dist[nx][ny]:
                        dist[nx][ny] = new_effort
                        heapq.heappush(pq, (new_effort, nx, ny))
        
        return 0

public class Solution {
    public int MinimumEffortPath(int[][] heights) {
        int m = heights.Length, n = heights[0].Length;
        int[,] dist = new int[m, n];
        var pq = new PriorityQueue<(int effort, int x, int y), int>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = int.MaxValue;
            }
        }
        
        dist[0, 0] = 0;
        pq.Enqueue((0, 0, 0), 0);
        
        int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (pq.Count > 0) {
            var (effort, x, y) = pq.Dequeue();
            
            if (x == m - 1 && y == n - 1) {
                return effort;
            }
            
            if (effort > dist[x, y]) {
                continue;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i, 0], ny = y + dirs[i, 1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newEffort = Math.Max(effort, Math.Abs(heights[nx][ny] - heights[x][y]));
                    if (newEffort < dist[nx, ny]) {
                        dist[nx, ny] = newEffort;
                        pq.Enqueue((newEffort, nx, ny), newEffort);
                    }
                }
            }
        }
        
        return 0;
    }
}

var minimumEffortPath = function(heights) {
    const rows = heights.length;
    const cols = heights[0].length;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    const minHeap = [[0, 0, 0]]; // [effort, row, col]
    const efforts = Array(rows).fill().map(() => Array(cols).fill(Infinity));
    efforts[0][0] = 0;
    
    while (minHeap.length > 0) {
        minHeap.sort((a, b) => a[0] - b[0]);
        const [currentEffort, row, col] = minHeap.shift();
        
        if (row === rows - 1 && col === cols - 1) {
            return currentEffort;
        }
        
        if (currentEffort > efforts[row][col]) {
            continue;
        }
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                const newEffort = Math.max(currentEffort, Math.abs(heights[newRow][newCol] - heights[row][col]));
                
                if (newEffort < efforts[newRow][newCol]) {
                    efforts[newRow][newCol] = newEffort;
                    minHeap.push([newEffort, newRow, newCol]);
                }
            }
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型Dijkstra算法二分查找+BFS
时间复杂度O(mn log(mn))O(mn log(max_height))
空间复杂度O(mn)O(mn)

其中 m 和 n 分别是网格的行数和列数。Dijkstra算法的时间复杂度主要来自于优先队列的操作，每个节点最多入队一次，每次出队和入队操作的时间复杂度是 O(log(mn))。

相关题目