最近算法哥哥很久没有更新了。 我一直在忙着做事情。 我今天也会继续分享有趣的算法问题。

在

题目描述

nn的栅格网格中，每个栅格的值grid[i][j]表示平台在位置(I，j )处的高度。

现在开始下雨了。 时间为t时，此时雨水引起的池塘任意位置的水位为t。 虽然可以从一个平台游到周围相邻的任意平台，但是前提是水位必须同时淹没两个平台。 假设可以瞬间移动无限的距离。 也就是说，默认在方格内部游泳是不需要时间的。 当然，你游泳的时候必须在网格里。

你从坐标方格左上角的平台(0，0 )出发。 到达坐标方格右下平台(N-1，N-1 )需要多长时间？

样本1:

输入3360 0，2，1，3

输出： 3

说明：

时间为0时，你坐标方格中的位置为(0，0 )。

此时不能向任意方向游泳。 因为四个相邻方向的平台高度大于当前时间为0时的水位。

到了3点以后，你就可以去站台(1，1 )游泳了。 这时的水位是3，坐标格子中的平台没有比水位3高的，所以可以游到坐标格子中的任意位置

样本2:

3360 [ 0，1，2，3，4 ]，24，23，22，21，5，12，13，14，15，16，11，17，18，19，20，10，20

输入： 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

最终的路线用粗体标记。

要保证平台(0，0 )和) 4，4 )相连，必须等待时间达到16分钟

提示：

2=n=50 .栅格[ I ] [ j ]位于区间[0，N*N – 1]内。 主题： leet代码778.swim in rising water

主题为

题目分析

，目的是在给定的水位上，能否瞬间从网格的左上角游到网格的右下角。 关于这样的主题，BFS的算法很容易考虑，但是主题需要最低水位。 如此想来，水位为level的情况下，如果能从grid的左上角游到grid的右下角，level 1的水位也一定很好吧。 因此，将等级的值分为2个，用BFS验证该等级是否可行，如果可能的话，可以在比等级小的范围内，否则可以在比等级大的范围内寻找可行的解！ 其实，二分搜索的答案思路在前面文章的每日算法LeetCode719中找到第二小距离对(难度系数2/5 )和每日算法LeetCode410 :分割数组的最大值)难度系数2/5 )中也有介绍，所以

源代码：

源代码

复杂度分析

二分搜索的复杂度为log(n ) n )，每次BFS验证的复杂度为n ) n，所以总责任度为o ) n^2) log ) n ) ) ) ) )，n在50以下，所以可以接受！

在

总结

这个主题下，我们再次看到了两分钟搜索答案的算法技巧解决算法问题时的妙计。 其实，二分思想在解决这样的问题时，往往有一个单调性，只要满足单调性就可以尝试二分搜索。 那么，单调性是什么呢？ 简单地说，如果某个解满足要求，那么比它大(小)的解也满足，那个时候就可以使用二分搜索的算法

主题共享结束后，请关注算法哥哥。 你的关注，转发，点赞，收藏是算法哥哥最大的鼓励。