本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優化，還會用多種編程語言實現題解，涉及到通用解法時更將歸納總結出相應的算法模板。

為了方便在PC上運行調試、分享代碼文件，我還建立了相關的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結等，還可以看到原題出現頻率和相關企業等重要信息。如果有其他優選題解，還可以一同分享給他人。

由于本系列文章的內容隨時可能發生更新變動，歡迎關注和收藏征服LeetCode系列文章目錄一文以作備忘。

你準備參加一場遠足活動。給你一個二維?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] <= 10^6

---

同類題目：

• LeetCode 2812. Find the Safest Path in a Grid
• LeetCode 778. Swim in Rising Water
• LeetCode 1631. 最小體力消耗路徑

這幾道題，雖然物理問題不同，但是背后的數學模型幾乎完全相同，唯一的區別在于：

• 第 1631 題將相鄰格子的高度差作為邊的權重，是找最小化的 相鄰格子最大絕對高度差。
• 第 778 題將相鄰兩格子間高度的最大值作為邊的權重，是找最小化的 最大高度
• 第 2812 題將當前方格到最近小偷的距離作為邊的權重，是找最大化的 最小距離

無向圖 $G$ 中 $x$ 到 $y$ 的最小瓶頸路是這樣的一類簡單路徑，滿足這條路徑上的最大邊權在所有 $x$ 到 $y$ 的簡單路徑中是最小的。
根據最小生成樹定義，$x$ 到 $y$ 的最小瓶頸路上的最大邊權等于最小生成樹上 $x$ 到 $y$ 路徑上的最大邊權。雖然最小生成樹不唯一，但是每種最小生成樹 $x$ 到 $y$ 路徑的最大邊權相同且為最小值。也就是說，每種最小生成樹上的 $x$ 到 $y$ 的路徑均為最小瓶頸路。

無向圖 $G$ 中 $x$ 到 $y$ 的最大瓶頸路是這樣的一類簡單路徑，滿足這條路徑上的最小邊權在所有 $x$ 到 $y$ 的簡單路徑中是最大的。
根據最小生成樹定義，$x$ 到 $y$ 的最大瓶頸路上的最小邊權等于最大生成樹上 $x$ 到 $y$ 路徑上的最小邊權。雖然最大生成樹不唯一，但是每種最大生成樹 $x$ 到 $y$ 路徑的最小邊權相同且為最大值。也就是說，每種最大生成樹上的 $x$ 到 $y$ 的路徑均為最大瓶頸路。

我們不必實際求出整個最小/大生成樹，只需要求出最小/大生成樹上 $x$ 到 $y$ 路徑上的最大/小邊權。

在看清楚物理問題背后的數學模型后，這幾道題都會迎刃而解。

解法1 二分+BFS/DFS

這種做法是LeetCode 2812. Find the Safest Path in a Grid的完全簡化版、在2812中需要先進行一次多源BFS、再來二分答案，也用在LeetCode 1631. 最小體力消耗路徑中。

根據題目中的描述，給定了 $heights[i][j]$ 的范圍是 $[1,10^6]$ ，所以答案（絕對高度差）必然落在范圍 $[0,10^6]$ ：

• 如果允許消耗的體力值 $h$ 越低，網格上可以越過的部分就越少，存在從左上角到右下角的一條路徑的可能性越小
• 如果允許消耗的體力值 $h$ 越高，網格上可以游泳的部分就越多，存在從左上角到右下角的一條路徑的可能性越大。

這是本問題具有的 單調性 。因此可以使用二分查找定位到最小體力消耗值。

假設最優解為 $l$ 的話（恰好能到達右下角的體力消耗），那么小于 $l$ 的體力消耗無法到達右下角，大于 $l$ 的體力消耗能到達右下角，因此在以最優解 $l$ 為分割點的數軸上具有二段性，可以通過「二分」找到分割點 $l$ 。

注意：「二分」的本質是兩段性，并非單調性。只要一段滿足某個性質，另外一段不滿足某個性質，就可以用「二分」。其中 33. 搜索旋轉排序數組 是一個很好的說明例子。

具體來說：在區間 $[0,1e6]$ 里猜一個整數，針對這個整數從起點（左上角）開始做一次DFS或BFS：

• 當小于等于該數值時，如果存在一條從左上角到右下角的路徑，說明答案可能是這個數值，也可能更小；
• 當小于等于該數值時，如果不存在一條從左上角到右下角的路徑，說明答案一定比這個數值更大。
• 按照這種方式不斷縮小搜索的區間，最終找到最小體力消耗。

class Solution {
public:int minimumEffortPath(vector<vector<int>>& heights) {int n = heights.size(), m = heights[0].size();typedef pair<int, int> pii;int d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};auto check = [&](int lim) {bool vis[n][m]; memset(vis, false, sizeof(vis));queue<pii> q;q.push(pii(0, 0)); vis[0][0] = true;while (!q.empty()) {pii p = q.front(); q.pop();int i = p.first, j = p.second;if (i == n - 1 && j == m - 1) return true;for (int k = 0; k < 4; ++k) {int x = i + d[k][0], y = j + d[k][1];if (x < 0 || x >= n || y < 0 || y >= m || abs(heights[x][y] - heights[i][j]) > lim || vis[x][y])continue;q.push(pii(x, y));vis[x][y] = true;}}return vis[n - 1][m - 1];};int l = 1, r = 1e6 + 1;while (l < r) {int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;}
};

復雜度分析：

• 時間復雜度：$O(MN\log C)$ 。 其中 $N,M$ 是方格的邊長。最差情況下進行 $\log C(C=1e6)$ 次二分查找，每一次二分查找最差情況下要遍歷所有單元格一次，時間復雜度為 $O(MN)$ 。
• 空間復雜度：$O(MN)$ 。 數組 $vis$ 的大小為 $MN$ ，如果使用深度優先遍歷，須要使用的棧的大小最多為 $MN$ ，如果使用廣度優先遍歷，須要使用的隊列的大小最多為 $MN$ 。

---

解法2 最小瓶頸路模型+最小生成樹（Prim+堆/Kruskal+邊集數組）

根據題意，我們要找的是從左上角到右下角的最優路徑，其中最優路徑是指途徑的邊的最大權重值最小，然后輸出最優路徑中的最大權重值。此處的邊權為途徑節點間高度差絕對值。

根據最小瓶頸路模型，我們可以使用Kruskal最小生成樹算法：

1. 先遍歷所有的點，將所有的邊加入集合，存儲的格式為數組 $[a,b,w]$ ，代表編號為 $a$ 的點和編號為 $b$ 的點之間的權重為 $w$（按照題意，$w$ 為兩者的高度絕對差）。
2. 對邊集集合進行排序，按照 $w$ 進行從小到達排序。
3. 當我們有了所有排好序的候選邊集合之后，對邊從前往后處理，選擇那些不會出現環的邊加入最小生成樹中。
4. 每次加入一條邊之后，使用并查集來查詢左上角點和右下角點是否連通。如果連通，那么該邊的權重即是答案。

class Solution {private class UnionFind {private int[] parent;public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; ++i) parent[i] = i;}public int find(int x) {return x != parent[x] ? parent[x] = find(parent[x]) : x;}public boolean isConnected(int x, int y) { return find(x) == find(y); }public void union(int p, int q) {int rp = find(p), rq = find(q);if (rp == rq) return;parent[rp] = rq;}}public int minimumEffortPath(int[][] grid) {int n = grid.length, m = grid[0].length;int len = n * m;int[][] d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};UnionFind unionFind = new UnionFind(len);// 預處理所有無向邊// edge存[a,b,w]: 代表從a到b所需的時間點為w// 雖然我們可以往四個方向移動,但只要對于每個點都添加「向右」和「向下」// 兩條邊的話，其實就已經覆蓋了所有邊List<int[]> edges = new ArrayList<>();for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {int index = i * m + j;int a, b, w;if (i + 1 < n) {a = index; b = (i + 1) * m + j;w = Math.abs(grid[i][j] - grid[i + 1][j]);edges.add(new int[]{a, b, w});}if (j + 1 < m) {a = index; b = i * m + (j + 1);w = Math.abs(grid[i][j] - grid[i][j + 1]);edges.add(new int[]{a, b, w});}   }}Collections.sort(edges, (a, b) -> a[2] - b[2]); // 根據w權值升序// 從「小邊」開始添加,當某一條邊應用之后,恰好使得「起點」和「結點」聯通// 那么代表找到了「最短路徑」中的「權重最大的邊」int start = 0, end = len - 1;for (int[] edge : edges) {int a = edge[0], b = edge[1], w = edge[2];unionFind.union(a, b);if (unionFind.isConnected(start, end)) return w;}return 0;}
}

Kruskal雖然沒有求出完整最小生成樹，但是對所有邊進行了排序。我們可以使用Prim算法+優先隊列。

下面將此問題抽象為一張帶權有向圖，每個單元格為頂點，有指向相鄰頂點的有向邊，邊的權值為指向頂點的高度絕對差。然后用Prim算法，求出最小生成樹上左上角的點到右下角的點的路徑上的最大邊權值。此時不用對所有邊進行排序。

class Solution {public int minimumEffortPath(int[][] grid) {int n = grid.length, m = grid[0].length;boolean[][] vis = new boolean[n][m];// 必須將 先前加入隊列時的邊權重 加入int[]中Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[2] - b[2]);minHeap.offer(new int[]{0, 0, 0});int[][] dist = new int[n][m];for (int[] row : dist)Arrays.fill(row, Integer.MAX_VALUE);dist[0][0] = 0;int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};while (!minHeap.isEmpty()) { // 找最短的邊int[] front = minHeap.poll();int x = front[0], y = front[1], d = front[2];if (vis[x][y]) continue;vis[x][y] = true;if (x == n - 1 && y == m - 1) break;// 更新for (int i = 0; i < 4; ++i) {int u = x + directions[i][0], v = y + directions[i][1];if (u >= 0 && u < n && v >= 0 && v < m && !vis[u][v] && // prim算法Math.max(d, Math.abs(grid[x][y] - grid[u][v]))<= dist[u][v]) {dist[u][v] = Math.max(d,Math.abs(grid[x][y] - grid[u][v]));minHeap.offer(new int[]{u, v, dist[u][v]});}}}return dist[n - 1][m - 1];}
}

復雜度分析：

• 時間復雜度：$O(MN\log MN)$ 。 使用了優先隊列的 Prim 算法的時間復雜度是 $O(E\log E)$ ，這里 $E$ 是邊數，至多是頂點數的 $4$ 倍，頂點數為 $MN$ ，因此 $O(E\log E)=O(4MN\log MN)=O(MN\log MN)$ 。
• 空間復雜度：$O(MN)$ 。 數組 $vis$ 、$dist$ 的大小為 $O(MN)$ ，優先隊列中保存的邊的總數也是 $MN$ 級別的。