【刷穿 LeetCode】1631. 最小体力消耗路径（中等）

宫水三叶的刷题日记

发布于 2021-02-20 09:42:03

6590

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。

一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。

你每次可以往上，下，左，右四个方向之一移动，你想要找到耗费体力最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。请你返回从左上角走到右下角的最小体力消耗值。

示例 1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

输入：heights = [[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]]
输出：0
解释：上图所示路径不需要消耗任何体力。

提示：

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106

并查集解法

由于在任意点可以往任意方向移动，所以相邻的点之间存在一条无向边。

我们可以先遍历所有的点，将所有的边加入集合，存储的格式为数组 [a, b, w] ，代表编号为 a 的点和编号为 b 的点之间的权重为 w（按照题意，w 为两者的高度差的绝对值）。

对集合进行排序，按照 w 进行从小到达排序。

当我们有了所有排好序的候选边集合之后，我们可以对边从前往后处理，每次加入一条边之后，使用并查集来查询左上角的点和右下角的点是否连通。

当我们的合并了某条边之后，判定左上角和右下角的点联通，那么该边的权重即是答案。

class Solution {
    int N = 10009;
    int[] p = new int[N];
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    boolean query(int a, int b) {
        return p[find(a)] == p[find(b)];
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    int row, col;
    public int minimumEffortPath(int[][] heights) {
        row = heights.length;
        col = heights[0].length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int idx = getIndex(i, j);
                p[idx] = idx;
                if (i + 1 < row) edges.add(new int[]{idx, getIndex(i + 1, j), Math.abs(heights[i][j] - heights[i + 1][j])});
                if (j + 1 < col) edges.add(new int[]{idx, getIndex(i, j + 1), Math.abs(heights[i][j] - heights[i][j + 1])});
            }
        }
        Collections.sort(edges, (a,b)->a[2]-b[2]);
        int start = getIndex(0, 0), end = getIndex(row - 1, col - 1);
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1], w = edge[2];
            union(a, b);
            if (query(start, end)) return w;
        }
        return 0; 
    }
    int getIndex(int x, int y) {
        return x * col  + y;
    }
}

令行数为 r，列数为 c，那么节点的数量为 r * c，无向边的数量严格为 r * (c - 1) + c * (r - 1)，数量级上为 r * c。

时间复杂度：获取所有的边复杂度为

O(r * c)

，排序复杂度为

O((r * c)\log{(r * c)})

，遍历得到最终解复杂度为

O(r * c)

。整体复杂度为

O((r * c)\log{(r * c)})

。

空间复杂度：使用了并查集数组。复杂度为

O(r * c)

证明

我们使用反证法来证明一下为什么这样的做法是对的。

我们假设「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是 w 最大的边」不成立：

我们令循环终止前的最后一条边为 a

假设 a 不在最优路径内：如果 a 并不在最优路径内，即最优路径是由 a 边之前的边构成，那么 a 边不会对左上角和右下角节点的连通性产生影响。也就是在遍历到该边之前，左上角和右下角应该是联通的，逻辑上循环会在遍历到该边前终止。与我们循环的决策逻辑冲突。
a 在最优路径内，但不是 w 最大的边：我们在遍历之前就已经排好序。与排序逻辑冲突。

得证「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是 w 最大的边」。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法