LeetCode 1631. 最小体力消耗路径

约 8 分钟
文章信息 8 个分类 7 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 阿里
标签
数组 深度优先搜索 广度优先搜索 二分查找 矩阵 堆（优先队列） 并查集

题目描述

✅ 1631. 最小体力消耗路径

image-20260928230734428

image-20260928230734429

image-20260928230734430

image-20260928230734431

题意分析

从左上角走到右下角，每步可以向上下左右相邻格子移动。单步消耗是两个格子高度差的绝对值，整条路径的体力消耗是所有单步消耗中的最大值。

求能达到的最小路径消耗。这里不累加沿途差值，也不要求步数最少，绕路可能更省力。单格矩阵已经位于终点，没有经过边，答案为零。

解法：Dijkstra 最小化最大边权

核心思路

[!blue]

将格子看成图节点，相邻格子间的边权为高度差。定义 dist[row][col] 为目前找到的、到达该格子的最小路径消耗。起点为零，其他格子先设为无穷大。

若已用消耗 effort 到达当前格子，再经过高度差为 step 的一条边，新路径消耗是 max(effort, step)。它若小于邻格现有记录，就改进邻格距离，并把新记录放入按消耗升序排列的最小堆。

普通 Dijkstra 用加法延伸路径，这里改成取最大值仍然成立：延伸路径不会降低已有消耗。每次取出的有效记录是所有待处理候选中最小的；若还存在一条更优路径，它从已确定区域首次走向未确定区域时，就应产生一个更小的候选并优先出堆，矛盾。因此有效出堆时，该格子的消耗已经最优。

同一格子可能先找到较差路线，随后又被改进，旧记录仍会留在堆中。弹出后先与 dist 比较，不一致就跳过。首次以有效记录取出终点时可以直接返回，因为此时终点距离已经确定，而不是第一次发现终点或第一次入堆就返回。

所有格子均可通行，有限网格中起终点存在连接；搜索会找到最优路径。

解题步骤

  1. 初始化距离表，起点为零，其余为无穷大；将起点放入最小堆。
  2. 弹出消耗最小的记录，过期记录直接跳过。
  3. 若当前格子是终点，返回当前消耗。
  4. 枚举四个合法邻格，用当前消耗和单步高度差的最大值生成候选。
  5. 候选更优时更新距离并入堆，继续处理。

代码实现

class Solution {
    // 到达某个格子的最优体力值，取决于此前路径体力值与最后一步高度差的较大值。
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        int[][] dist = new int[rows][cols];

        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

        dist[0][0] = 0;
        minHeap.offer(new int[] {
            0,
            0,
            0
        });
        int[][] dirs = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1},
        };

        while (!minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            int effort = cur[0];
            int row = cur[1];
            int col = cur[2];

            // 更好路线已经更新距离，这条堆记录过期。
            if (effort != dist[row][col]) {
                continue;
            }

            if (row == rows - 1 && col == cols - 1) {
                return effort;
            }

            for (int[] dir : dirs) {
                int nextRow = row + dir[0];
                int nextCol = col + dir[1];

                if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) {
                    continue;
                }

                int step = Math.abs(heights[row][col] - heights[nextRow][nextCol]);
                // 路径代价取最大的单步高度差，不是沿途求和。
                int nextEffort = Math.max(effort, step);

                if (nextEffort < dist[nextRow][nextCol]) {
                    dist[nextRow][nextCol] = nextEffort;
                    minHeap.offer(new int[] {
                        nextEffort,
                        nextRow,
                        nextCol
                    });
                }
            }
        }

        return 0;
    }
}

import "container/heap"

type item struct {
    effort int
    row    int
    col    int
}

type minHeap []item

func (h minHeap) Len() int {
    return len(h)
}

func (h minHeap) Less(i int, j int) bool {
    return h[i].effort < h[j].effort
}

func (h minHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *minHeap) Push(x any) {
    *h = append(*h, x.(item))
}

func (h *minHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func minimumEffortPath(heights [][]int) int {
    rows, cols := len(heights), len(heights[0])
    dist := make([][]int, rows)
    for i := range dist {
        dist[i] = make([]int, cols)
        for j := range dist[i] {
            dist[i][j] = 1 << 30
        }
    }

    h := &minHeap{}
    heap.Push(h, item{effort: 0, row: 0, col: 0})
    dist[0][0] = 0
    dirs := [][]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }
    for h.Len() > 0 {
        cur := heap.Pop(h).(item)
        // 更好路线已经更新距离，这条堆记录过期。
        if cur.effort != dist[cur.row][cur.col] {
            continue
        }
        if cur.row == rows-1 && cur.col == cols-1 {
            return cur.effort
        }

        for _, dir := range dirs {
            nextRow := cur.row + dir[0]
            nextCol := cur.col + dir[1]
            if nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols {
                continue
            }

            step := absInt(heights[cur.row][cur.col] - heights[nextRow][nextCol])
            // 路径代价取最大的单步高度差，不是沿途求和。
            nextEffort := maxInt(cur.effort, step)
            if nextEffort < dist[nextRow][nextCol] {
                dist[nextRow][nextCol] = nextEffort
                heap.Push(h, item{effort: nextEffort, row: nextRow, col: nextCol})
            }
        }
    }

    return 0
}

func absInt(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(mn\log(mn+1))$。网格有 $mn$ 个节点，每格至多四条邻边，松弛与堆操作总规模为线性乘对数。
  • 空间复杂度：$O(mn)$，用于距离表和待处理堆记录。

关键点总结

[!green]

  • 路径延伸使用最大值，准确表示沿途最困难的一步。
  • 延伸不会使路径消耗下降，最小堆出堆的有效记录可以确定最优值。
  • 同一位置允许被更优路线更新，过期堆记录随后忽略。
  • 终点有效出堆才可结束，首次入堆还不代表最优。

易错点总结

[!yellow]

  • 累加单步高度差求的是另一种路径目标，不能替代取最大值。
  • 第一次发现某格就永久标记，会阻止之后更好的路线改进它。
  • 使用队列按步数层次搜索，不能直接保证这种加权瓶颈代价最小。
  • 距离默认零会让所有正消耗候选无法更新，非起点需要初始化为足够大。
  • 最短步数或几何距离最短与最小体力没有等价关系。

相似题目

题目 难度 关联与区别
778. 水位上升的泳池中游泳 困难 同样最小化路径上的最大瓶颈，原题看格子高度，本题看相邻格子的高度差。
1584. 连接所有点的最小费用 中等 按边权递增做并查集合并时，起终点首次连通的权值给出本题瓶颈；原题继续连接全部点求总成本。
743. 网络延迟时间 中等 用优先队列取当前最优距离并松弛邻边；本题路径代价改为沿途最大边权，该题传播源点到各点的加法距离。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/24095551
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！