1631. 最小体力消耗路径

• 题号：1631
• 来源：LeetCode
• 难度：中等
• 标签：图 dp 堆
• 语言：TypeScript
• 解法：2 个
• 作者：lmliheng
• 最近更新：2026-09-27

解法一

TypeScript · O(m*n) 时间 · O(m*n) 空间 · 更新于 2026-09-27

注释自述 dp 不成立，路径可回头，此解错误

/**
 * @difficulty medium
 * @tags 图,dp
 * @time O(m*n)
 * @space O(m*n)
 * @note 注释自述 dp 不成立，路径可回头，此解错误
 * @1631. 最小体力消耗路径
 */

/**
 * @dp
 *
 * @lc1631最小体力消耗路径
 * @https://leetcode.cn/problems/path-with-minimum-effort/description/
 *
 * @不能使用dp，路径没有规定只能左到右，上到下
 *
 */

let heights: number[][] = [[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]]
let m: number = heights.length
let n: number = heights[0].length

let dp: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(Infinity))
// 初始化
dp[0][0] = 0
for (let i: number = 1; i < m; i++) {
    if (dp[i - 1][0] < Math.abs(heights[i][0] - heights[i - 1][0])) {
        dp[i][0] = Math.abs(heights[i][0] - heights[i - 1][0])
    } else {
        dp[i][0] = dp[i - 1][0]
    }
}

for (let i: number = 1; i < n; i++) {
    if (dp[0][i - 1] < Math.abs(heights[0][i] - heights[0][i - 1])) {
        dp[0][i] = Math.abs(heights[0][i] - heights[0][i - 1])
    } else {
        dp[0][i] = dp[0][i - 1]
    }
}

// 可以往回走
for (let i: number = 1; i < m; i++) {
    for (let j: number = 1; j < n; j++) {
        // 比一条路大 比另一条小
        // 比两条大
        let d1: number = dp[i - 1][j] < Math.abs(heights[i][j] - heights[i - 1][j]) ? Math.abs(heights[i][j] - heights[i - 1][j]) : dp[i - 1][j]
        let d2: number = dp[i][j - 1] < Math.abs(heights[i][j] - heights[i][j - 1]) ? Math.abs(heights[i][j] - heights[i][j - 1]) : dp[i][j - 1]
        let d3: number = dp[i + 1][j] < Math.abs(heights[i][j] - heights[i][j - 1]) ? Math.abs(heights[i][j] - heights[i][j - 1]) : dp[i][j - 1]
        dp[i][j] = Math.min(d1, d2)
    }
}

console.log(dp)

export {};

源码：ts/leetcode/1631. 最小体力消耗路径.ts

解法二 · TypeScript

TypeScript · O(m*n*log(m*n)) 时间 · O(m*n) 空间 · 更新于 2026-09-27

手写最小堆做类 Dijkstra，边权取相邻高差

/**
 * @difficulty medium
 * @tags 图,堆
 * @time O(m*n*log(m*n))
 * @space O(m*n)
 * @note 手写最小堆做类 Dijkstra，边权取相邻高差
 * @1631. 最小体力消耗路径（解法二）
 */

/**
 * @最小堆
 */

interface HeapNode {
    effort: number;
    row: number;
    col: number;
}

class MinHeap {
    heap: HeapNode[];

    constructor() {
        this.heap = [];
    }

    isEmpty(): boolean {
        return this.heap.length === 0;
    }

    push(node: HeapNode): void {
        this.heap.push(node);
        this._bubbleUp(this.heap.length - 1);
    }

    pop(): HeapNode | null {
        if (this.isEmpty()) return null;
        const min: HeapNode = this.heap[0];
        const last: HeapNode = this.heap.pop()!;
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this._sinkDown(0);
        }
        return min;
    }

    _bubbleUp(index: number): void {
        while (index > 0) {
            const parentIndex: number = Math.floor((index - 1) / 2);
            if (this.heap[index].effort >= this.heap[parentIndex].effort) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    _sinkDown(index: number): void {
        const length: number = this.heap.length;
        while (true) {
            let smallest: number = index;
            const leftChild: number = 2 * index + 1;
            const rightChild: number = 2 * index + 2;

            if (leftChild < length && this.heap[leftChild].effort < this.heap[smallest].effort) {
                smallest = leftChild;
            }
            if (rightChild < length && this.heap[rightChild].effort < this.heap[smallest].effort) {
                smallest = rightChild;
            }
            if (smallest === index) break;

            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }
}



let heights: number[][] = [[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]]
const rows: number = heights.length;
const cols: number = heights[0].length;

// 方向数组：右、下、左、上
const dirs: number[][] = [[0, 1], [1, 0], [0, -1], [-1, 0]];

// 距离数组，记录到达每个点的最小体力消耗
const dist: number[][] = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
dist[0][0] = 0;

// 最小堆：[effort, row, col]
const heap: MinHeap = new MinHeap();
heap.push({ effort: 0, row: 0, col: 0 });

while (!heap.isEmpty()) {
    const { effort: d, row: r, col: c } = heap.pop()!;

    // 如果已经到达右下角，返回结果
    if (r === rows - 1 && c === cols - 1) console.log(dist);

    // 如果当前距离大于已知最短距离，跳过
    if (d > dist[r][c]) continue;

    for (const [dr, dc] of dirs) {
        const nr: number = r + dr;
        const nc: number = c + dc;

        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
            // 计算相邻格子的高度差
            const effort: number = Math.abs(heights[nr][nc] - heights[r][c]);
            // 新的路径最大体力消耗
            const newDist: number = Math.max(d, effort);

            if (newDist < dist[nr][nc]) {
                dist[nr][nc] = newDist;
                heap.push({ effort: newDist, row: nr, col: nc });
            }
        }
    }
}

console.log(dist)

export {};

源码：ts/leetcode/1631. 最小体力消耗路径（解法二）.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm