解题思路

要保证能跨过河流，只要保证能跨过最长的两个石头间隙即可，这就是答案

代码

def find_minimum_max_step(n, river):
    last_stone = -1

1000ms

Difficulty: 2

所属公司 : oppo

算法与标签>贪心算法

有一条长度为 $n$ 的河流，小O初始位于左岸边（即河流左侧的岸边）。他想要跨越到河对岸（即河流右侧的岸边）。河上有一些石头可以让小O踩在上面。小O只能踩在石头或者岸边，他想知道他至少能够到达对岸的情况下，最长的一步最短是多少。

第一行输入一个整数 $n$ ( $1 \leq n \leq 2 \times 10^5$ ) 代表河流的长度。
第二行输入 $n$ 个整数数组 $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i \leq 1$ ) 代表是否是石头， $a_i = 1$ 说明当前位置是石头，可以踩；否则为水流，不能踩。

在一行上输出一个整数，表示最长的一步的最小值。

5
0 1 1 0 1

如下图所示，最长的一步至少为2，因为从左岸边跨越到最近的石头距离为2。

6
0 0 0 0 0 1

编辑器加载中…

输入

预期输出（选填）