最小体力消耗路径(LC1631)
哪些公司问过
答案要点
- 网格建图,边权为相邻格高度差绝对值
- 目标为最小化路径上的最大边权
- Dijkstra 变体:新代价 = max(当前代价, 边权),终点出堆即答案
- 二分答案 + BFS 判断连通
- 边按权排序 + 并查集,起终点连通时的边权即答案
易错点
- 把代价写成高度差之和,求成了普通最短路
- 用 DFS 枚举所有路径,指数级超时
- 出堆时没有跳过已经过期的旧状态
面试官常见追问
- 为什么取 max 的代价也能用 Dijkstra?
- 三种方法的复杂度对比?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。