跳到主要内容

LeetCode 1631. 最小体力消耗路径

本节目标

用瓶颈代价 Dijkstra 最小化一条网格路径上的最大高度差。

这是图论综合中“路径代价改为瓶颈”的母题。走过相邻格子的代价是高度差，但一条路径的体力消耗取其中最大的那条边。

查看 LeetCode 原题

题意与约束​

从左上走到右下，每步可上下左右移动。跨越相邻高度 a、b 的边代价是 |a-b|；整条路径代价不是边权之和，而是路径中最大边权，要求这个最大值尽量小。

直接思路与瓶颈​

枚举所有网格路径数量随格子数急剧增加；把高度差直接相加则优化了错误的目标，可能错过“总和较大但最大落差较小”的路径。需要记录到每格的最小可达瓶颈，并优先扩展当前瓶颈最小的状态。

图模型与算法推导​

每个格子是顶点，相邻格子间有权为高度差的边。effort[row][col] 表示到该格子的最小瓶颈；从当前瓶颈 current 跨边 diff 后，候选为 max(current, diff)。最小堆按候选瓶颈取点，过期堆项跳过，终点首次出堆即可返回。

正确性依据​

对任意扩展，max(current, diff) 不会小于已有瓶颈，满足 Dijkstra 所需的单调性。堆顶是所有未确定状态中瓶颈最小的候选；若存在到该格子更小瓶颈的路径，其前缀会先以不更大的键值被处理并松弛它，矛盾。因此终点首次出堆时的值最优。

样例执行过程​

对 [[1,2,2],[3,8,2],[5,3,5]]，堆先取 (0,0,0)，产生 (1,0,1)、(2,1,0)；取 (1,0,1) 后产生 (1,0,2) 和 (6,1,1)。再取 (1,0,2)，可到 (1,1,2)；随后 (1,1,2) 到 (2,2,2) 的候选为 max(1,|2-5|)=3，而经左下路径会把终点更新为 2，最终终点以瓶颈 2 出堆。

代码实现​

C++17
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        const int rows = static_cast<int>(heights.size());
        const int cols = static_cast<int>(heights[0].size());
        const long long INF = 1LL << 60;
        vector<vector<long long>> effort(rows, vector<long long>(cols, INF));
        priority_queue<tuple<long long, int, int>,
                       vector<tuple<long long, int, int>>,
                       greater<tuple<long long, int, int>>> heap;
        const vector<pair<int, int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        effort[0][0] = 0;
        heap.push({0, 0, 0});

        while (!heap.empty()) {
            auto [current, row, col] = heap.top();
            heap.pop();
            if (current != effort[row][col]) {
                continue;
            }
            if (row == rows - 1 && col == cols - 1) {
                return static_cast<int>(current);
            }

            for (const auto& [dr, dc] : dirs) {
                const int nxtRow = row + dr;
                const int nxtCol = col + dc;
                if (nxtRow < 0 || nxtRow >= rows || nxtCol < 0 || nxtCol >= cols) {
                    continue;
                }
                const long long candidate = max(
                    current,
                    abs(static_cast<long long>(heights[row][col]) -
                        static_cast<long long>(heights[nxtRow][nxtCol])));
                if (candidate < effort[nxtRow][nxtCol]) {
                    effort[nxtRow][nxtCol] = candidate;
                    heap.push({candidate, nxtRow, nxtCol});
                }
            }
        }

        return 0;
    }
};

复杂度分析​

网格有 mn 个顶点和 O(mn) 条相邻边，每次松弛都可能入堆，时间 O(mn log(mn))；effort 和堆使用 O(mn) 空间。

边界与易错点​

  • 单个格子没有经过边，答案为 0。
  • 不能累加高度差；新状态是 max(current, diff)。
  • 只保留当前边差会丢失前缀中的更大瓶颈。
  • 堆中可能有过期候选，弹出后要比对 effort。

模式迁移​

当风险由最危险环节、链路由最弱一段决定时，把路径聚合由求和改为取最大值，仍可用最小堆维护最优瓶颈状态。