#2498
Frog Jump II
specialist · 685 · lc medium +30 · verified · 62.4% accepted · 870 likes · top 64%
Description
Given a strictly increasing array stones of stone positions in a river, a frog starts on the first stone, travels to the last stone, and returns to the first stone — visiting each stone at most once. The cost of the round trip is the maximum single-jump length taken across all jumps. Return the minimum possible cost.
Example 1:
Input: stones = [0,2,5,6,7]
Output: 5
Explanation: The above figure represents one of the optimal paths the frog can take.
The cost of this path is 5, which is the maximum length of a jump.
Since it is not possible to achieve a cost of less than 5, we return it.
Example 2:
Input: stones = [0,3,9]
Output: 9
Explanation:
The frog can jump directly to the last stone and come back to the first stone.
In this case, the length of each jump will be 9. The cost for the path will be max(9, 9) = 9.
It can be shown that this is the minimum achievable cost.
Code
1
2
3