LeetCode 778. 水位上升的泳池中游泳 题目描述 在一个 n x n 的整数矩阵 grid 中，每个单元格的值表示该位置的高度。假设此时开始下雨，当时间为 t 时，水池中的水位高度为 t 。你可以从任意一个单元格出发，并游向相邻（上下左右）的任意一个单元格，但要求是你当前所在单元格和目的单元格的高度都必须不超过 t （即两个单元格都不被淹没）。请你找出从左上角 (0,0) 到达右下角 (n-1, n-1) 所需的最少时间。注意：时间 t 必须满足你能够游到终点。 通俗理解 随着时间推移，水位从 0 开始逐渐上升。 你只能在高度 ≤ 当前水位的格子之间游动。 要求找到最小的 t ，使得在时间为 t 时，存在一条从起点到终点的路径。 解题思路 这个问题本质是寻找最小的 t ，使得当水位为 t 时，起点和终点连通（所有路径上的格子高度 ≤ t ）。 我们可以用 二分查找 + BFS/DFS 或 并查集 来解决。 方法一：二分查找 + BFS 二分查找的上下界 下界：起点和终点的最大值（因为必须能站在这两个格子上）。 上界：所有格子中的最大值（因为当 t 达到最大值时，所有格子都可通行）。 检查函数 check(t) 使用 BFS 遍历网格，只能访问高度 ≤ t 的格子。 如果从 (0,0) 能到达 (n-1, n-1) ，说明时间 t 可行。 二分过程 在 [low, high] 范围内二分查找最小的可行 t 。 详细步骤 初始化 low = max(grid[0][0], grid[n-1][n-1]) ， high = 所有格子最大值 。 当 low < high ： 取 mid = (low + high) / 2 。 执行 BFS 检查是否在 t = mid 时可从起点到终点： 创建一个访问矩阵 visited 。 从 (0,0) 开始，将相邻且高度 ≤ mid 的格子加入队列。 如果到达终点，说明 mid 可行，令 high = mid 。 否则 low = mid + 1 。 返回 low 。 复杂度分析 时间复杂度：O(n² log M)，其中 M 是高度范围。 空间复杂度：O(n²)。 方法二：并查集 按高度排序所有边 将每个格子看作图中的一个节点，相邻格子之间的边权为两个格子高度的最大值。 将所有边（相邻格子对）按权值排序。 逐步合并 从最小的边开始，依次将边加入并查集。 每次加入一条边后，检查起点和终点是否连通。 当起点和终点连通时，当前边的权值就是答案。 详细步骤 创建并查集，包含 n² 个节点。 构建边列表： 对于每个格子 (i, j) ，与右边 (i, j+1) 和下边 (i+1, j) 的边权为 max(grid[i][j], grid[相邻]) 。 按边权从小到大排序。 遍历边列表： 合并边的两个端点。 检查 find(0) 和 find(n²-1) 是否连通。 如果连通，返回当前边权。 复杂度分析 时间复杂度：O(n² log n)（排序主导）。 空间复杂度：O(n²)。 总结 二分+BFS 更直观，适合理解问题本质。 并查集 更高效，利用了边权单调性。 两种方法都能在合理时间内解决问题，你可以根据偏好选择实现。