985. Frog Round Trip
Stones lie in a straight line across a pond at the positions listed in stones, in strictly increasing order. A frog starts on the first stone, travels forward to the last stone, and then travels back to the first stone. Apart from the first and last stones, which are the start and the turnaround, every stone may be landed on at most once during the whole round trip.
The cost of a trip is its longest single jump, measured as the distance between the two stones. Return the smallest possible cost over all valid round trips. A jump may skip any number of stones.
Example 1
- Input:
- stones = [0,3,5,9]
- Output:
- 6
- Explanation:
One best route goes 0 → 3 → 9 and comes back 9 → 5 → 0: jumps 3, 6, 4, 5, so the longest is 6, and no route does better.
Example 2
- Input:
- stones = [2,4,10]
- Output:
- 8
- Explanation:
With three stones the middle one can be used only once, so the frog must jump between the two end stones in one direction: 10 - 2 = 8.
Constraints
- 2 ≤ stones.length ≤ 105
- 0 ≤ stones[0] < stones[1] < ... < stones[n - 1] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)