LeetCode 1631. 最小体力消耗路径

2026-05-14 HGNULB 约 11 分钟

文章信息 8 个分类 8 个标签

分类

题目描述

✅ 1631. 最小体力消耗路径

题意分析

给一张高度图，人从左上角走到右下角，每步只能上下左右挪一格。要求在所有可行路线里挑一条，使这条路线的「体力值」最小。

最容易读错的就是体力值的定义：它不是把沿途所有高度差加起来，而是取沿途相邻两格高度差绝对值里的最大那一个。换句话说，一条路线的好坏由它最陡的那一步单独决定，其余步骤陡不陡完全不影响得分。

这个定义带来两个直接后果。一是绕远路不受惩罚，只要绕开的那几格都很平缓，多走一百步也不比走两步差；二是代价不具备可加性，沿途累计的量只增不减且是取最大值，这和常见的「路径长度求和」是两种不同的合成方式。

边界方面：网格至少 $1 \times 1$，此时起点即终点，一步不用走，答案是 0；高度可以完全相同，答案也是 0；行列都不超过 100，格子总数最多一万，允许对每个格子做带排序的处理。

解法：Dijkstra 最小化最大边权

核心思路

暴力做法是枚举所有从左上到右下的路径，对每条路径取最大高度差再取全局最小。由于允许绕路甚至上下折返，路径条数随格子数指数增长，光是枚举就跑不完。

瓶颈在于把「路径」当成了枚举对象。换个角度：对每个格子只关心一个量——从起点走到它的所有路线中，最陡一步的最小可能值，记作 $dist[r][c]$。这就是本题的状态定义。答案就是 $dist[m-1][n-1]$。

状态之间的转移是：若从 $(r, c)$ 迈一步到相邻的 $(nr, nc)$，这一步的陡度是 $ h[r][c] - h[nr][nc] $，那么这条路线的最大陡度变成 $\max(dist[r][c], step)$。合成算子从「加法」换成了「取最大值」，但它和加法共享两条关键性质：对第一个参数单调不减，且结果永远不小于 $dist[r][c]$ 本身。

正是这两条性质保证了贪心式扩展成立。不变量：每当从最小堆里弹出一个非过期状态时，它记录的体力值就是该格子的最终答案，之后不会再被任何路线改进。理由是堆里剩下的候选体力值都不小于它，而经过它们再走一步只会让 $\max$ 更大或持平，绝无可能把已弹出的值压低。

这就是把 Dijkstra 从「最小化路径和」搬到「最小化路径瓶颈」上，堆里存三元组 $(effort, row, col)$，按 $effort$ 升序弹出，终点第一次被弹出时即可收工。

解题步骤

开 dist 矩阵并全部填成极大值，把 dist[0][0] 置 0，起点三元组 {0, 0, 0} 入堆。起点还没迈过任何一步，最大陡度自然是 0；其余格子填极大值是为了让第一次松弛必然成功。

循环从堆里弹出体力值最小的三元组。用最小堆而不是普通队列，是因为「先确定小的」是本解法正确性的全部依据。

弹出后先检查 effort != dist[row][col]，成立就跳过。这里用的是惰性删除：一个格子可能被多次改进并多次入堆，只有和当前 dist 相符的那份是最新的，其余都是过期副本，直接丢弃比在堆里做 decrease-key 简单得多。

若弹出的正是右下角，立刻返回它的 effort。此时它已被确定为最优，继续跑完整个堆纯属浪费。

否则枚举上下左右四个方向，先做越界判断，再算 step = |h[row][col] - h[nextRow][nextCol]| 和 nextEffort = max(effort, step)。取绝对值是因为上坡下坡同样费力；取 max 是因为体力值由最陡一步决定。

只有 nextEffort < dist[nextRow][nextCol] 时才更新并入堆。这个条件同时承担两件事：它是松弛判定，也是天然的去重——严格变小才入堆，保证同一格子入堆次数有限。

网格连通，终点必然会被弹出，末尾的 return 0 只是为了让编译器满意；顺带也覆盖了 $1 \times 1$ 网格的退化情形。

以 heights = [[1,2,2],[3,8,2],[5,3,5]] 走一遍：弹出 $(0,0,0)$，向下到 $(1,0)$ 陡度 $ 1-3 =2$，dist[1][0] = 2；向右到 $(0,1)$ 陡度 1，dist[0][1] = 1。弹出 $(1,0,1)$，向右到 $(0,2)$ 陡度 $ 2-2 =0$，取 $\max(1,0)=1$，dist[0][2] = 1；向下到 $(1,1)$ 陡度 $ 2-8 =6$，dist[1][1] = 6。弹出 $(1,0,2)$，向下到 $(1,2)$ 陡度 0，$\max(1,0)=1$，dist[1][2] = 1。弹出 $(1,1,2)$，向下到 $(2,2)$ 陡度 $ 2-5 =3$，$\max(1,3)=3$，dist[2][2] = 3；向左到 $(1,1)$ 得 $\max(1,6)=6$，不小于 6，不更新。弹出 $(2,1,0)$，向下到 $(2,0)$ 陡度 $ 3-5 =2$，$\max(2,2)=2$，dist[2][0] = 2；向右到 $(1,1)$ 陡度 $ 3-8 =5$，$\max(2,5)=5 < 6$，dist[1][1] 改成 5，堆里那份 6 就此作废。弹出 $(2,2,0)$，向右到 $(2,1)$ 陡度 $ 5-3 =2$，$\max(2,2)=2$，dist[2][1] = 2。弹出 $(2,2,1)$，向右到 $(2,2)$ 陡度 $ 3-5 =2$，$\max(2,2)=2 < 3$，dist[2][2] 降为 2 并再次入堆。下一次弹出 $(2,2,2)$，effort 与 dist[2][2] 相符且正是右下角，返回 2。对应路线是沿左下绕行的 $(0,0) \to (1,0) \to (2,0) \to (2,1) \to (2,2)$，高度依次为 $1, 3, 5, 3, 5$，四步的陡度都是 2，虽然更长，但最陡一步只有 2。

代码实现

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;
    }
}

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))$，格子数是 $mn$，每个格子每被松弛成功一次就入堆一次，边数是 $4mn$ 级别，所以入堆总次数是 $O(mn)$，每次堆操作 $O(\log (mn))$。

空间复杂度：$O(mn)$，dist 矩阵占 $mn$，堆里同时可能存在 $O(mn)$ 个未清理的状态副本，方向数组是常数。

关键点总结

「最小化路径上的最大边权」是最短路的一个变体，只要把松弛式里的 dist + w 换成 max(dist, w) 就能复用 Dijkstra 的全部框架，因为这个算子同样满足单调不减。

Dijkstra 成立的真正条件不是「边权为正」，而是「延长路径不会让代价变小」。想清楚这一点，遇到瓶颈路、乘积路径等变体才敢下手。

惰性删除是标准堆优化写法：不做 decrease-key，而是允许同一节点多份副本入堆，弹出时用 effort != dist[r][c] 把过期副本筛掉。

终点一出堆就返回，比跑完整个堆再读 dist 更快，前提是先确认「出堆即最优」这条不变量成立。

面试视角：这题至少有三种解法——Dijkstra 变形、二分答案加连通性判定、并查集按边权从小到大合并直到首尾连通。能主动报出三条路线并比较各自复杂度，比闷头写完一种更能拿分；面试官常追问的正是「为什么这里的 Dijkstra 还成立」。

易错点总结

错误写法：把体力值当成路径上高度差之和累加，即 nextEffort = effort + step → heights = [[1,2,3],[3,8,4],[5,3,5]] 这类图上会选中总和小但存在陡坡的路线，输出的数值和题意完全不是一回事。

错误写法：算 step 时忘记取绝对值 → 下坡产生负数，max 直接把它忽略，于是从高处往低处的落差不计费，答案偏小。

错误写法：用普通队列或栈替代最小堆做 BFS/DFS → 弹出顺序与体力值无关，「先弹出即最优」的前提消失，会得到某条可行路线的体力值而非最小值。

错误写法：省掉 effort != dist[row][col] 的过期判断 → 逻辑上仍能算出正确答案，但每个过期副本都会再展开一轮邻居，堆规模和运行时间显著膨胀，大网格上有超时风险。

错误写法：改用 visited 布尔数组，弹出即标记且永不重入 → 与惰性删除混用时会把还能被改进的格子提前封死；本题若在入队时就标记 visited，dist[1][1] 从 6 降到 5 的那次改进就发生不了。

错误写法：松弛条件写成 nextEffort <= dist[nextRow][nextCol] → 相等也入堆，平坦区域里同值状态互相反复入堆，堆无限增长直至超时。

错误写法：在入堆时判断是否到达终点并立即返回 → 返回的是某条路线的体力值而不是最小值，因为该状态还没经过堆的排序确认。

错误写法：dist 初值用 Integer.MAX_VALUE 之后又对它做加法 → 本题的 max 不会溢出，但若照搬到求和版最短路上就会整数回绕，习惯上应初始化成 1 << 30 这类安全大数。

错误写法：单元素网格 heights = [[1]] 时忘了起点即终点 → 若把终点判断写在扩展邻居之后，起点被弹出时不检查，四个方向全越界，堆空后落到兜底返回，虽然本题兜底恰好是 0，换个兜底值就是错的。

相似题目

题目	难度	考察点
499. 迷宫 III	困难	距离相同时还要比较路径字典序，需在堆里加第二关键字
505. 迷宫 II	中等	球一直滚到撞墙才算一条边，边权是滚动格数
743. 网络延迟时间	中等	邻接表上的标准求和最短路，答案取全体距离的最大值
778. 水位上升的泳池中游泳	困难	同为瓶颈路，代价换成格子高度本身而非相邻差值
787. K 站中转内最便宜的航班	中等	中转次数上限破坏了贪心，需改用按层松弛的 Bellman-Ford
1334. 阈值距离内邻居最少的城市	中等	点数少但要全源距离，Floyd 的三重循环比多次建堆更省事