各位题友大家好，今天是每日算法题公众号坚持日更的第 6 天。今天力扣上的每日一题是第 778 题「778. 水位上升的泳池中游泳」。可以通过每日一题的小程序查看题目详情：

题目大意

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

定义路径耗时：一条路径中所有节点的最大高度。

求坐标方格的左上平台 (0，0) 出发，到达坐标方格的右下平台 (N-1, N-1) 的所有路径中的路径耗时最小值。

示例：

输入: [[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
解释:
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，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

数据范围：

  1. 2 <= N <= 50.
  2. grid[i][j] 是 [0, ..., N*N - 1] 的排列。

    解题思路

从左上角通往右下角的路径中，消耗的时间肯定是道路上最高的那个格子的高度。对于这种问题，也是像昨天题目一样，当做连通性问题来解决。

判断是否连通常见的办法是：并查集。

昨天的每日一题为「1631. 最小体力消耗路径」，它是求从左上角到右下角的所有路径中的最小高度差绝对值，跟本题非常像。建议大家先阅读昨天的题解：1631. 最小体力消耗路径。

今天题目和昨天题目的不同之处：

  • 昨天的题目是把相邻的两个格子之间的高度差的绝对值当作了边的权重，对边排序，逐渐添加边，看添加到哪个边的时候，起点和终点能连通；
  • 今天的题目中，由于不用求高度差，而是求路径上的格子高度的最大值，因此，可以把抽象成为一个边的权重为 0 的无向图，然后对顶点排序，逐个添加上每个顶点，看添加到哪个点的时候，起点和终点能连通。

需要注意题目中的一个条件：grid[i][j] 是 [0, ..., N*N - 1] 的排列。因此图中没有大小相等的顶点。

整体思路是：

  1. 先去除图中的所有顶点，然后按照顶点数值的从小到大的顺序，依次遍历并添加每个顶点；
  2. 在每次遍历的过程中都要比较这个顶点的数值和其周围的 4 个相邻顶点的数值大小，来判断是否需要添加一条边：如果相邻节点的数值更小，说明该相邻顶点之前已经添加到图中，因此现在需要建立一条让两个顶点连通的边；如果相邻节点的数值更大，说明该相邻顶点之前没有添加到图中，因此不要建立连通的边。
  3. 当添加某一个顶点之后，最左上角的顶点和最右下角的顶点连通了，说明该顶点就是所求。

整个流程就如下面的动画所示（该动画来自力扣官方题解，地址：https://leetcode-cn.com/problems/swim-in-rising-water/solution/shui-wei-shang-sheng-de-yong-chi-zhong-y-862o/）：

【每日一题】778. 水位上升的泳池中游泳 - 图1

代码

代码讲解：

  1. 先遍历了每个顶点，使用 nodes 数组来保存[0, ..., N*N - 1] 的排列中，每个数字出现的位置。
  2. 然后对 nodes 数组遍历，含义就是从小到大的数值顺序，依次添加上每个顶点，判断该顶点的四个方向的顶点是否需要跟自身连通（四个方向的顶点没有出图的边界，而且数值比当前顶点的数值小）。
  3. 当相邻顶点和当前顶点连通之后，如果最左上角的顶点和最右下角的顶点连通，则停止搜索，返回当前顶点的数值。

使用 Python2 写的代码如下。

  1. class Solution(object):
  2.     def swimInWater(self, grid):
  3.         """
  4.         :type grid: List[List[int]]
  5.         :rtype: int
  6.         """
  7.         N = len(grid)
  8.         nodes = [None] * (N * N)
  9.         for i in range(N):
  10.             for j in range(N):
  11.                 nodes[grid[i][j]] = (i, j)
  12.         dsu = DSU(N * N)
  13.         dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  14.         for i, node in enumerate(nodes):
  15.             x, y = node[0], node[1]
  16.             for dir in dirs:
  17.                 newx = x + dir[0]
  18.                 newy = y + dir[1]
  19.                 if newx >= 0 and newx < N and newy >= 0 and newy < N and grid[newx][newy] < i:
  20.                     dsu.union(x * N + y , newx * N + newy)
  21.             if dsu.connected(0, N * N - 1):
  22.                 return i
  23.         return 0
  25. class DSU:
  26.     def __init__(self, size):
  27.         self.par = range(size)
  29.     def find(self, x):
  30.         if x != self.par[x]:
  31.             self.par[x] = self.find(self.par[x])
  32.         return self.par[x]
  34.     def union(self, x, y):
  35.         self.par[self.find(x)] = self.find(y)
  37.     def connected(self, x, y):
  38.         return self.find(x) == self.find(y)

刷题心得

本题原本的题面是个假设了一个下雨的场景，求下雨多久，才能左上角的位置游到右下角的位置。这种题面需要我们有抽象能力，即把题目中生活化的语言翻译成我们能理解的专业语言。比如我在题目大意中已经进行了对题目进行了翻译。题目抽象出来之后，能帮助我们决定用什么方法。

今天的题目除了并查集方法之外，还能使用 BFS 或者 二分查找 + DFS 的方法，由于篇幅问题，就不展开了。可以在 负雪明烛 的 CSDN 上查看，地址是：https://blog.csdn.net/fuxuemingzhu/article/details/82926674

OK，这就是本次题解的全部内容了，如果你觉得我的题解对你有帮助的话，求赞、求关注、求转发、求在看。你的认可就是我前进的最大动力！我们明天再见！

欢迎加入组织

算法每日一题是个互相帮助、互相监督的力扣打卡网站，其地址是 https://www.ojeveryday.com/

想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击「加入组织」，提交力扣个人主页，即可进入刷题群。期待你早日加入。

也可点击「阅读原文」，直接提交力扣个人主页。

题目来源：778. 水位上升的泳池中游泳，

https://leetcode-cn.com/problems/swim-in-rising-water