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

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

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

在一個 n x n 的整數矩陣 grid 中，每一個方格的值 grid[i][j] 表示位置 (i, j) 的平臺高度。

當開始下雨時，在時間為 t 時，水池中的水位為 t 。你可以從一個平臺游向四周相鄰的任意一個平臺，但是前提是此時水位必須同時淹沒這兩個平臺。假定你可以瞬間移動無限距離，也就是默認在方格內部游動是不耗時的。當然，在你游泳的時候你必須待在坐標方格里面。

你從坐標方格的左上平臺 (0，0) 出發。返回 你到達坐標方格的右下平臺 (n-1, n-1) 所需的最少時間 。

示例 1:

輸入: grid = [[0,2],[1,3]]
輸出: 3
解釋:
時間為0時，你位于坐標方格的位置為 `(0, 0)。`
此時你不能游向任意方向，因為四個相鄰方向平臺的高度都大于當前時間為 0 時的水位。
等時間到達 3 時，你才可以游向平臺 (1, 1). 因為此時的水位是 3，坐標方格中的平臺沒有比水位 3 更高的，所以你可以游向坐標方格中的任意位置

示例 2:

輸入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
輸出: 16
解釋: 最終的路線用加粗進行了標記。
我們必須等到時間為 16，此時才能保證平臺 (0, 0) 和 (4, 4) 是連通的

提示:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• grid[i][j] 中每個值 均無重復

---

注意題目中的重要信息：假定你可以 瞬間移動 無限距離，游動不耗時。當前這個問題就轉換成為：找一個時刻 $t$ ，使得這個二維網格上數值 小于等于 $t$ 的部分，存在一條從左上角到右下角的路徑。即：經過了時間 $t$ 以后，可以瞬間從左上角（坐標 $[0,0]$ ）游到右下角（坐標 $[N?1,N?1]$ ）。

相似題目：

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

解法1 二分+BFS/DFS

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

根據題目中的描述，給定了 $grid[i][j]$ 的范圍是 $[0,n^2?1]$ ，所以答案必然落在此范圍：

• 如果等待的時間 $t$ 越少，網格上可以游泳的部分就越少，存在從左上角到右下角的一條路徑的可能性越小
• 如果等待的時間 $t$ 越多，網格上可以游泳的部分就越多，存在從左上角到右下角的一條路徑的可能性越大。

這是本問題具有的 單調性 。因此可以使用二分查找定位到最短等待時間。

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

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

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

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

class Solution {
public:int swimInWater(vector<vector<int>>& grid) {int n = grid.size();typedef pair<int, int> pii;int d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};auto check = [&](int lim) { // 能否在<=lim時間從左上到右小bool vis[n][n]; memset(vis, false, sizeof(vis));queue<pii> q;if (grid[0][0] <= lim) {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 == n - 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 >= n || grid[x][y] > lim || vis[x][y])continue;q.push(pii(x, y));vis[x][y] = true;}}return vis[n - 1][n - 1];};int l = grid[0][0], r = n * n;while (l < r) {int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;}
};

復雜度分析：

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

---

解法2 計數排序+并查集

關于連通性的問題，如果只問結果，不問具體怎么連起來的，還可以考慮使用并查集。由于題目要找的是最少等待時間，可以模擬下雨的過程，把網格抽象成一個無權圖，每經過一個時刻，水位不斷提高，就考慮此時和雨水高度相等的單元格，考慮這個單元格的上、下、左、右、四個方向且高度更低的單元格，把它們在并查集中進行合并。

為了找到高度相近的單元格，需要先進行計數排序。注意 grid[i][j] 中每個值 均無重復 。

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 swimInWater(int[][] grid) {int n = grid.length;int len = n * n;int[] heightToIndex = new int[len]; // 方格的高度:方格的坐標for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)heightToIndex[grid[i][j]] = i * n + j;int[][] d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};UnionFind unionFind = new UnionFind(len);for (int i = 0; i < len; ++i) { // 高度從低到高int x = heightToIndex[i] / n, y = heightToIndex[i] % n;for (int j = 0; j < 4; ++j) {int u = x + d[j][0], v = y + d[j][1];if (u >= 0 && u < n && v >= 0 && v < n && grid[u][v] <= i)unionFind.union(heightToIndex[i], u * n + v); // 合并}if (unionFind.isConnected(0, len - 1)) return i; // 連通}return -1;}
}

這種做法部分類似LeetCode 2812. Find the Safest Path in a Grid的并查集做法——每輪將「到最近小偷的距離為 $x$ 的單元格」與「距離為 $x+1$ 的單元格」合并。

復雜度分析：

• 時間復雜度：$O(N^2\log N)$ 。 其中 $N$ 是方格的邊長。計數排序 $O(N^2)$ ，合并周圍、檢查起點和終點是否屬于同個連通分量 $O(\log N^2)$ 。總的時間復雜度為 $O(N^2+N^2\log N^2)=O(N^2+2N^2\log N)=O(N^2\log N)$ 。
• 空間復雜度：$O(N^2)$ 。 數組 index 的大小為 $N^2$ ，并查集底層的長度均為 $N^2$ 。

---

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

根據題意，我們要找的是從左上角到右下角的最優路徑，其中最優路徑是指途徑的邊的最大權重值最小，然后輸出最優路徑中的最大權重值。

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

這道題和第 1631 題，雖然物理問題不同，但是背后的數學模型幾乎完全相同，唯一的區別在于第 1631 題將相鄰格子的高度差作為邊的權重、而本題將相鄰兩格子間高度的最大值作為邊的權重。在看清楚物理問題背后的數學模型后，這兩道題的物理問題都會迎刃而解。

和1631. 最小體力消耗路徑幾乎是完全一樣的思路。我們不必實際求出整個最小生成樹，只需要求出最小生成樹上 $x$ 到 $y$ 路徑上的最大邊權。

根據最小瓶頸路模型，我們可以使用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 swimInWater(int[][] grid) {int n = grid.length;int len = n * n;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 < n; ++j) {int index = i * n + j;int a, b, w;if (i + 1 < n) {a = index; b = (i + 1) * n + j;w = Math.max(grid[i][j], grid[i + 1][j]);edges.add(new int[]{a, b, w});}if (j + 1 < n) {a = index; b = i * n + (j + 1);w = Math.max(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算法，求出最小生成樹上左上角的點到右下角的點的路徑上的最大邊權。此時不用對所有邊進行排序。

Prim算法在示例2的用法如下：

class Solution {public int swimInWater(int[][] grid) {int n = grid.length;Queue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> grid[o[0]][o[1]]));minHeap.offer(new int[]{0, 0});boolean[][] vis = new boolean[n][n];// dist[i][j]表示 到頂點[i,j] 要等待的最少時間int[][] dist = new int[n][n];for (int[] row : dist) Arrays.fill(row, n * n);dist[0][0] = grid[0][0];int[][] d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};while (!minHeap.isEmpty()) { // 找最短的邊int[] front = minHeap.poll();int x = front[0], y = front[1];if (vis[x][y]) continue;vis[x][y] = true;if (x == n - 1 && y == n - 1) return dist[n - 1][n - 1];// 更新for (int i = 0; i < 4; ++i) {int u = x + d[i][0], v = y + d[i][1];if (u >= 0 && u < n && v >= 0 && v < n && !vis[u][v] && // prim算法Math.max(dist[x][y], grid[u][v]) < dist[u][v]) {dist[u][v] = Math.max(dist[x][y], grid[u][v]);minHeap.offer(new int[]{u, v});}}}return -1;}
}

復雜度分析：

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