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的整数矩阵gridgrid[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. 方案一暴力 DFSBrute Force直觉暴力枚举从起点到终点的每一条可行路径。对每条路径维护一个截至目前踩过的最大高度t到达终点时返回该值对所有路径取最小值即为答案。算法步骤从(0, 0)出发初始时间t 0对单元格(r, c)越界或已访问 → 返回一个很大的数无效路径更新t max(t, grid[r][c])站在该格所需的水位若是终点(n-1, n-1)→ 返回t标记(r, c)为已访问递归尝试上、下、左、右四个方向取四个递归结果的最小值从当前位置出发的最佳路径回溯取消标记返回该最小值。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。算法步骤计算网格最小值minH与最大值maxH定义canReach(t)从(0,0)做 DFS禁止进入越界、已访问、或高度 t的格子能到达(n-1, n-1)即返回true令t从minH遍历到maxH第一个canReach(t) true的t即为答案每次尝试后必须重置 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. 方案三二分答案 DFSBinary Search DFS直觉canReach(t)具有单调性这是二分答案成立的前提如果水位t能到达终点那么任何更高的水位t1, t2, ...也一定能到达开放的格子只会更多如果水位t不能到达那么任何更低的水位也不能。因此可以对答案t做二分搜索每次用 DFS 验证当前mid是否可行。算法步骤搜索范围low 网格最小值high 网格最大值定义canReach(t)DFS 只走高度 t的格子逻辑与方案二相同二分mid (low high) // 2若canReach(mid)为真 → 尝试更小水位high mid否则 → 需要更多水low mid 1每次验证前后重置 visited当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 的定义变为到达某格子的成本 迄今为止路径上最小的最大高度。算法步骤用最小堆存状态(timeSoFar, r, c)其中timeSoFar 到达(r, c)的路径最大高度初始入堆(grid[0][0], 0, 0)循环弹出timeSoFar最小的状态若到达终点直接返回timeSoFar最小堆保证这是最优值对四个邻居若合法且未访问计算newTime max(timeSoFar, grid[nr][nc])并入堆用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])仓库中的多语言佐证Ccpp/0778-swim-in-rising-water.cpp 使用priority_queue实现并对n 1的边界直接返回0同时以max(grid[0][0], grid[n-1][n-1])作为初始结果Javajava/0778-swim-in-rising-water.java 同样在len 1时返回0用PriorityQueueInteger[]按高度排序TypeScripttypescript/0778-swim-in-rising-water.ts 使用MinPriorityQueue入堆时即计算Math.max(grid[nr][nc], weight)Rustrust/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 式把所有格子整理为(height, r, c)并按height升序排序初始化N*N个节点的 DSU节点编号id r*N c按高度从小到大依次处理每个格子当前格子(r, c)在时刻t height变为开放对四个邻居若邻居高度 t已开放或同时开放执行union每次 union 后检查起点0与终点N*N-1是否连通首次连通时的t即为答案返回该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 Pitfallsarticles/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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考