LeetCode 778. 水位上升的泳池中游泳 题目描述 在一个 N x N 的坐标方格 grid 中，每个方格的值 grid[i][j] 表示在位置 (i, j) 的平台高度。现在开始下雨，时间为 t 时，你可以游到 任意 一个坐标方格，只要此时该方格的水位不低于 t （即 grid[i][j] <= t ）。你从坐标方格的左上角 (0, 0) 出发，要到达右下角 (N-1, N-1) 。请计算你 最早 在什么时间能够到达右下角。注意：你每次可以向上、下、左、右四个方向移动一个单位。 解题思路 这个问题可以理解为：寻找一个最小的 t ，使得存在一条从 (0, 0) 到 (N-1, N-1) 的路径，路径上所有方格的高度都不超过 t 。我们可以通过二分查找结合广度优先搜索（BFS）或深度优先搜索（DFS）来求解。 步骤详解 步骤1：理解问题核心 我们需要找到最小的 t ，使得在 t 时刻，存在一条从起点到终点的路径，且路径上所有方格的高度 ≤ t 。 因为时间 t 是单调递增的，我们可以用二分查找来快速确定最小的 t 。 步骤2：确定二分查找的范围 最小可能时间 left ：起点的高度 grid[0][0] （因为必须能站在起点）。 最大可能时间 right ：网格中的最大高度值（因为当 t 达到最大值时，所有方格都可通行）。 在二分查找过程中，我们检查中间值 mid 是否可行。 步骤3：定义检查函数（BFS/DFS） 对于给定的 t ，检查是否存在从 (0, 0) 到 (N-1, N-1) 的路径，路径上所有点的高度 ≤ t 。 使用 BFS 或 DFS 遍历网格，从起点开始，只访问高度 ≤ t 的相邻方格。 如果能够到达终点，说明 t 可行，我们尝试更小的 t ；否则，需要更大的 t 。 步骤4：二分查找执行过程 初始化 left = grid[0][0] ， right = max_value （网格中的最大值）。 当 left < right 时： 计算 mid = (left + right) // 2 。 检查 mid 是否可行（通过 BFS/DFS）。 如果可行，则 right = mid （尝试更小的时间）。 否则， left = mid + 1 （需要更大时间）。 最终 left 即为答案。 步骤5：检查函数的实现（以 BFS 为例） 使用队列存储待访问坐标，集合记录已访问坐标。 从 (0, 0) 开始，如果其高度 ≤ t ，则入队。 每次从队列取出一个坐标，检查其四个方向的相邻坐标： 如果相邻坐标在网格内、未被访问过、且高度 ≤ t ，则标记为已访问并入队。 如果到达 (N-1, N-1) ，返回 True ；否则队列为空时返回 False 。 为什么这样有效？ 二分查找快速缩小时间范围，避免线性搜索。 BFS 确保在可行的情况下找到路径，且每次检查的时间复杂度为 O(N²)。 整体时间复杂度为 O(N² log M)，其中 M 是高度范围，通常高效。 通过以上步骤，你可以逐步理解并实现这个问题的解决方案。