[LeetCode]Swim in Rising Water

图的连接性的问题，第一个想法就是Union Find，Union Find的具体讲解可以参考这篇文章。因为高度的范围是[0, n^2 - 1]，我们只需要先遍历所有edge，因为有的edge是到特定的高度才会出现，所以我们建立高度到edges的映射。从0到n^2 - 1遍历所有高度，每次加入对应的edges，知道发现起点和终点连通了，我们就找到了满足条件的最小高度。时间复杂度O(n^2 * log* n)，我们总共有n^2 * (n^2 - 1) / 2条遍，union find的每次操作时间复杂度为O(log* n)，空间复杂度O(n^2)，代码如下：



可以看到Union Find方法的某些缺点，如果高度的范围太大，union find就会很不效率。但是这也给我们提供了一个很好的思路，为什么我们要顺序的搜索最小的高度呢？如果我们binary search，显然我们知道答案所在的范围为[minHeignt, maxHeignt]，我们也有O(n^2)的方法来验证给定height，从起点能否到终点。显然二分也是一个很好的方法，时间复杂O(n^2 * log(n))，空间复杂度 worst case O(n^2)，代码如下：


除此之外我们还有用类似Dijkstra的解法。我们用f(v)表示从起点到当前节点v所经过的最大高度，我们可以看出f(v)是沿路径递增的。那么我们可以用类似的方法证明Dijkstra也可以用来求到节点v的最小f(v)的值，证明如下：

• 对于v = start node，显而易见最小的f(v)就是起始节点的高度
• 假设存在set = {v1, v2,...,vi}，我们求得了set中所有节点的最小f(v)值。那么对于我们即将从priority queue上展开的下一个节点vk，其对应的值就是最小的f(vk)值
• 我们可以明确的是priority queue上对应的值，是set中所有路径到达vk的最小f(vk)值
• 假设存在另一条路径通过set之外某个节点vj到达vk，并且这条路径上的f(vk)值比priority queue上对应的值要小。那么由于f(v)在路径上是递增的，那么显然vj要比vk更先被展开，这与我们的假设“vj是set之外的某个节点”矛盾

时间复杂度O(n^2 log n)，最坏的情况可能展开n^2个node，时间复杂度O(n^2)，代码如下：