leetcode 项目精讲：Swim in Rising Water（水位上升泳池）五类解法与最小化路径最大值的图论建模

leetcode 项目精讲：Swim in Rising Water（水位上升泳池）五类解法与最小化路径最大值的图论建模

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术指南围绕 LeetCode 经典题778. Swim in Rising Water（水位上升的泳池中游泳）展开，以本仓库 hints/swim-in-rising-water.md 的解题提示为骨架，系统讲解从暴力 DFS 到 Dijkstra、Kruskal 的完整解法演进。读者学完后将掌握"最小化路径上的最大值"这类 minimax 路径问题的建模思路，并能独立用贪心堆、二分答案、并查集等策略写出多语言实现。

---

1. 问题定义与核心洞察

给定一个n x n的整数矩阵grid，grid[i][j]表示坐标(i, j)处的地势高度。雨水落下后，在时刻t，整个网格的水深均为t。你从左上角(0, 0)出发，目标是到达右下角(n-1, n-1)，并且只有当两个相邻格子的高度都不超过t时才能游过去；游泳本身不消耗时间，但你可能需要在水位上涨到足够高之前原地等待。

需要返回的是：能够从起点游到终点的最小等待时间。

1.1 把矩阵看成图

正如 hints/swim-in-rising-water.md 的 Hint 1 所指出的：把每个格子视为一个节点，相邻格子之间连边。当水位为t时，只有高度<= t的格子才是"开放"的，路径只能穿过这些开放格子。

1.2 关键洞察：路径成本 = 路径上的最大高度

Hint 1 和 Hint 2 给出了本题最核心的观察：

一条路径所花费的时间，由该路径上所有格子的最大高度值决定。

因为你必须等水位涨到这条路上最高的那个格子那么高才能通行。因此问题被等价转化为：

找到一条从(0, 0)到(n-1, n-1)的路径，使得路径上格子的最大高度最小。

这就是典型的minimax（极小化极大）路径问题——标准最短路径算法（如 Dijkstra）在这里依然适用，只是"距离"的定义从"边权之和"变成了"路径上的最大边权"。

1.3 复杂度目标

根据 hints/swim-in-rising-water.md 的 Recommended Time & Space Complexity：

指标	目标
时间复杂度	O(n² log n)
空间复杂度	O(n²)

其中n是方阵的行（列）数。下面的 Dijkstra 与 Kruskal 方案正好达到该标准。

---

2. 方案一：暴力 DFS（Brute Force）

直觉

暴力枚举从起点到终点的每一条可行路径。对每条路径，维护一个"截至目前踩过的最大高度"t，到达终点时返回该值；对所有路径取最小值即为答案。

算法步骤

1. 从(0, 0)出发，初始时间t = 0；
2. 对单元格(r, c)：
   • 越界或已访问 → 返回一个很大的数（无效路径）；
   • 更新t = max(t, grid[r][c])（站在该格所需的水位）；
   • 若是终点(n-1, n-1)→ 返回t；
3. 标记(r, c)为已访问；
4. 递归尝试上、下、左、右四个方向；
5. 取四个递归结果的最小值（从当前位置出发的最佳路径）；
6. 回溯取消标记，返回该最小值。

Python 实现

class Solution: def swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) visit = [[False] * n for _ in range(n)] def dfs(node, t): r, c = node if min(r, c) < 0 or max(r, c) >= n or visit[r][c]: return 1000000 if r == (n - 1) and c == (n - 1): return max(t, grid[r][c]) visit[r][c] = True t = max(t, grid[r][c]) res = min(dfs((r + 1, c), t), dfs((r - 1, c), t), dfs((r, c + 1), t), dfs((r, c - 1), t)) visit[r][c] = False return res return dfs((0, 0), 0)

仓库同款实现可参考 python/0778-swim-in-rising-water.py（该文件内为下文方案四 Dijkstra 的实现），暴力 DFS 的多语言版本见 articles/swim-in-rising-water.md 第一节（Java/C++/JavaScript/C#/Go/Kotlin/Swift/Rust 均有）。

复杂度

• 时间：O(4^(n²))—— 路径数量随格子数指数爆炸，仅用于理解问题；
• 空间：O(n²)—— visited 矩阵与递归栈。

---

3. 方案二：DFS + 水位线性扫描

直觉

把问题改写成yes/no 判定问题：

"如果水位是t，我能不能从(0, 0)游到(n-1, n-1)？"

水位为t时，只允许踩grid[r][c] <= t的格子。于是从最小的可能高度开始，逐一把t加 1，返回第一个能到达终点的t。

算法步骤

1. 计算网格最小值minH与最大值maxH；
2. 定义canReach(t)：从(0,0)做 DFS，禁止进入越界、已访问、或高度> t的格子，能到达(n-1, n-1)即返回true；
3. 令t从minH遍历到maxH，第一个canReach(t) == true的t即为答案；
4. 每次尝试后必须重置 visited。

Python 实现

class Solution: def swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) visit = [[False] * n for _ in range(n)] minH = maxH = grid[0][0] for row in range(n): maxH = max(maxH, max(grid[row])) minH = min(minH, min(grid[row])) def dfs(node, t): r, c = node if (min(r, c) < 0 or max(r, c) >= n or visit[r][c] or grid[r][c] > t): return False if r == (n - 1) and c == (n - 1): return True visit[r][c] = True return (dfs((r + 1, c), t) or dfs((r - 1, c), t) or dfs((r, c + 1), t) or dfs((r, c - 1), t)) for t in range(minH, maxH): if dfs((0, 0), t): return t for r in range(n): for c in range(n): visit[r][c] = False return maxH

复杂度

• 时间：O(n⁴)—— 最多尝试O(n²)个水位，每个水位一次O(n²)的 DFS；
• 空间：O(n²)。

---

4. 方案三：二分答案 + DFS（Binary Search + DFS）

直觉

canReach(t)具有单调性（这是二分答案成立的前提）：

• 如果水位t能到达终点，那么任何更高的水位t+1, t+2, ...也一定能到达（开放的格子只会更多）；
• 如果水位t不能到达，那么任何更低的水位也不能。

因此可以对答案t做二分搜索，每次用 DFS 验证当前mid是否可行。

算法步骤

1. 搜索范围：low = 网格最小值，high = 网格最大值；
2. 定义canReach(t)（DFS 只走高度<= t的格子，逻辑与方案二相同）；
3. 二分：
   • mid = (low + high) // 2；
   • 若canReach(mid)为真 → 尝试更小水位high = mid；
   • 否则 → 需要更多水low = mid + 1；
   • 每次验证前后重置 visited；
4. 当low == high时即为最小所需时间。

Python 实现

class Solution: def swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) visit = [[False] * n for _ in range(n)] minH = maxH = grid[0][0] for row in range(n): maxH = max(maxH, max(grid[row])) minH = min(minH, min(grid[row])) def dfs(node, t): r, c = node if (min(r, c) < 0 or max(r, c) >= n or visit[r][c] or grid[r][c] > t): return False if r == (n - 1) and c == (n - 1): return True visit[r][c] = True return (dfs((r + 1, c), t) or dfs((r - 1, c), t) or dfs((r, c + 1), t) or dfs((r, c - 1), t)) l, r = minH, maxH while l < r: m = (l + r) >> 1 if dfs((0, 0), m): r = m else: l = m + 1 for row in range(n): for col in range(n): visit[row][col] = False return r

复杂度

• 时间：O(n² log n)—— 二分次数O(log n)，每次 DFSO(n²)；
• 空间：O(n²)。

---

5. 方案四：Dijkstra 算法（推荐，达成 Hint 3 的目标复杂度）

直觉

Hint 3 明确指出：用 Dijkstra 算法。初始化一个最小堆和一张"无穷大"矩阵，从源点(0, 0)开始运行，沿路径记录遇到的最大高度，并以此作为 Dijkstra 比较的键；一旦弹出终点(n-1, n-1)，即返回到达该点的路径上的最大高度。

把每个格子的高度理解为"允许你站在上面的最早时刻"。从起点到终点的路径总时间不是求和，而是路径上踩过的最大高度。于是 Dijkstra 的定义变为：

• 到达某格子的"成本" = 迄今为止路径上最小的"最大高度"。

算法步骤

1. 用最小堆存状态(timeSoFar, r, c)，其中timeSoFar= 到达(r, c)的路径最大高度；
2. 初始入堆(grid[0][0], 0, 0)；
3. 循环：
   • 弹出timeSoFar最小的状态；
   • 若到达终点，直接返回timeSoFar（最小堆保证这是最优值）；
   • 对四个邻居，若合法且未访问，计算newTime = max(timeSoFar, grid[nr][nc])并入堆；
4. 用visited集合保证每个格子只在"最优 timeSoFar"下被处理一次。

Python 实现

仓库 python/0778-swim-in-rising-water.py 提供了与本方案完全一致的可运行实现：

class Solution: def swimInWater(self, grid: List[List[int]]) -> int: N = len(grid) visit = set() minH = [[grid[0][0], 0, 0]] # (time/max-height, r, c) directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] visit.add((0, 0)) while minH: t, r, c = heapq.heappop(minH) if r == N - 1 and c == N - 1: return t for dr, dc in directions: neiR, neiC = r + dr, c + dc if ( neiR < 0 or neiC < 0 or neiR == N or neiC == N or (neiR, neiC) in visit ): continue visit.add((neiR, neiC)) heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])

仓库中的多语言佐证

• C++：cpp/0778-swim-in-rising-water.cpp 使用priority_queue实现，并对n == 1的边界直接返回0，同时以max(grid[0][0], grid[n-1][n-1])作为初始结果；
• Java：java/0778-swim-in-rising-water.java 同样在len == 1时返回0，用PriorityQueue<Integer[]>按高度排序；
• TypeScript：typescript/0778-swim-in-rising-water.ts 使用MinPriorityQueue，入堆时即计算Math.max(grid[nr][nc], weight)；
• Rust：rust/0778-swim-in-rising-water.rs 通过自定义State的Ord（反转比较实现最小堆）完成同样的贪心扩展；
• Go、C#、Kotlin、Swift 版本见 articles/swim-in-rising-water.md 第四节。

复杂度

• 时间：O(n² log n)；
• 空间：O(n²)。

---

6. 方案五：Kruskal 风格 + 并查集（Union-Find / DSU）

直觉

水位t随时间上涨：时刻t只允许踩高度<= t的格子，因此随着t增大，越来越多的格子"开放"，相邻开放格子聚成越来越大的连通区域。我们要求的是：起点(0,0)与终点(N-1,N-1)第一次处于同一连通分量的那个最早时刻t。

并查集（DSU）非常适合：它能快速合并相邻的开放格子，并随时检查起点与终点是否连通。

算法步骤（Kruskal 式）

1. 把所有格子整理为(height, r, c)并按height升序排序；
2. 初始化N*N个节点的 DSU，节点编号id = r*N + c；
3. 按高度从小到大依次处理每个格子：
   • 当前格子(r, c)在时刻t = height变为"开放"；
   • 对四个邻居，若邻居高度<= t（已开放或同时开放），执行union；
   • 每次 union 后检查起点0与终点N*N-1是否连通；
   • 首次连通时的t即为答案；
4. 返回该t。

Python 实现

class DSU: def __init__(self, n): self.Parent = list(range(n + 1)) self.Size = [1] * (n + 1) def find(self, node): if self.Parent[node] != node: self.Parent[node] = self.find(self.Parent[node]) return self.Parent[node] def union(self, u, v): pu = self.find(u) pv = self.find(v) if pu == pv: return False if self.Size[pu] < self.Size[pv]: pu, pv = pv, pu self.Size[pu] += self.Size[pv] self.Parent[pv] = pu return True def connected(self, u, v): return self.find(u) == self.find(v) class Solution: def swimInWater(self, grid: List[List[int]]) -> int: N = len(grid) dsu = DSU(N * N) positions = sorted((grid[r][c], r, c) for r in range(N) for c in range(N)) directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] for t, r, c in positions: for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < N and 0 <= nc < N and grid[nr][nc] <= t: dsu.union(r * N + c, nr * N + nc) if dsu.connected(0, N * N - 1): return t

复杂度

• 时间：O(n² log n)—— 排序O(n² log n)，路径压缩 + 按大小合并的 union 近似常数；
• 空间：O(n²)。

---

7. 常见陷阱（Common Pitfalls）

articles/swim-in-rising-water.md 末尾总结了本仓库解法中反复出现的五类易错点，值得单独强调：

7.1 把"时间"误当成"步数"

本题的时间不是路径长度，而是等待水位上升到路径最大高度所需的时间。步数再多，只要最大高度小，时间就短；反之亦然。

7.2 忘记计入起点和终点

答案至少是max(grid[0][0], grid[n-1][n-1])，因为你必须能站在两个端点上。仓库 C++/Java 实现以max(grid[0][0], grid[n-1][n-1])初始化结果，正是对这一点的工程化处理。

7.3 二分搜索边界设置错误

二分下界应取网格最小值（或至少grid[0][0]），上界取网格最大值。用0到n*n-1虽然可行，但精度更差、区间更大。

7.4 多次搜索之间忘记重置 visited

在线性扫描与二分两种 DFS 方案中，每次用新阈值t做 DFS 前都必须清空visited，否则上一次搜索的残留状态会导致错误结果。

7.5 并查集节点编号错误

Kruskal 方案中最常见的 bug 是 2D 坐标转 1D 索引不一致。必须统一使用r * N + c，并且只对"已开放"（高度<= 当前时刻）的邻居执行 union。

---

8. 五类解法速查对比

方案	核心思想	时间复杂度	空间复杂度	适用场景
暴力 DFS	枚举所有路径取最小最大高度	O(4^(n²))	O(n²)	仅用于理解题意
DFS + 线性扫描	判定式 + 逐水位尝试	O(n⁴)	O(n²)	小规模数据、演示单调性
二分答案 + DFS	二分水位 + DFS 判定	O(n² log n)	O(n²)	面试高频写法
Dijkstra（最小堆）	minimax 最短路径	O(n² log n)	O(n²)	推荐实现，直观易写
Kruskal + DSU	按高度排序并逐步合并连通分量	O(n² log n)	O(n²)	加深并查集与最小生成树理解

延伸思考

• 该题的本质是**最小瓶颈路径（minimax path）**问题：任意两点间"最小化最大边权"的路径，可以由最小生成树（MST）上的唯一路径给出，这正是 Kruskal 解法正确的理论依据；
• 同样的建模方式可迁移到"最大化最小边权""最小化最大海拔差"（如 Path With Minimum Effort）等题目，只需调整堆中的比较键与转移公式；
• 仓库的完整多语言解法、逐步骤算法说明与复杂度分析，可继续阅读 articles/swim-in-rising-water.md，并对照 cpp/0778-swim-in-rising-water.cpp、java/0778-swim-in-rising-water.java、rust/0778-swim-in-rising-water.rs 等 12 种语言实现进行验证与练习。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode