What is the main pattern to use in Frog Jump II?

Binary search over the valid answer space is the core pattern to minimize the maximum jump length.

Can the frog jump to the same stone more than once?

No, each stone can be visited at most once, including during the return trip.

How do I verify a candidate maximum jump?

Use a greedy traversal to simulate jumps forward and backward, ensuring no jump exceeds the candidate.

What if the stones array has large gaps?

Binary search will still identify the minimal maximum jump, but the greedy check may fail for large candidates.

What is the time complexity of the solution?

O(n log D), where n is the number of stones and D is the distance between the first and last stone.

#2498

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

青蛙过河 II

给你一个下标从 0 开始的整数数组 stones ，数组中的元素严格递增，表示一条河中石头的位置。一只青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头至多到达一次。一次跳跃的长度是青蛙跳跃前和跳跃后所在两块石头之间的距离。更正式的，如果青蛙从 st…

数组二分查找贪心

题目描述

给你一个下标从 0 开始的整数数组 stones ，数组中的元素 严格递增 ，表示一条河中石头的位置。

一只青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头至多到达 一次。

一次跳跃的长度是青蛙跳跃前和跳跃后所在两块石头之间的距离。

更正式的，如果青蛙从 stones[i] 跳到 stones[j] ，跳跃的长度为 |stones[i] - stones[j]| 。

一条路径的代价是这条路径里的 最大跳跃长度 。

请你返回这只青蛙的 最小代价 。

示例 1：

输入：stones = [0,2,5,6,7]
输出：5
解释：上图展示了一条最优路径。
这条路径的代价是 5 ，是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径，我们返回 5 。

示例 2：

输入：stones = [0,3,9]
输出：9
解释：
青蛙可以直接跳到最后一块石头，然后跳回第一块石头。
在这条路径中，每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。
这是可行路径中的最小代价。

提示：

2 <= stones.length <= 10⁵
0 <= stones[i] <= 10⁹
stones[0] == 0
stones 中的元素严格递增。

lightbulb

解题思路

方法一：脑筋急转弯

要使得跳跃过程中的每一步的最大跳跃长度最小，我们应该将跳跃过程切分成尽可能多的连续的步骤。通过观察，间隔跳跃可以获取最优解。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 stones 的长度。

1

2

3

4

5

6

7

class Solution:
    def maxJump(self, stones: List[int]) -> int:
        ans = stones[1] - stones[0]
        for i in range(2, len(stones)):
            ans = max(ans, stones[i] - stones[i - 2])
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log D), where D is the range between the first and last stone, as binary search tests each jump length and each check traverses all stones. Space complexity is O(1) extra beyond the input array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on validating jump lengths efficiently rather than enumerating all paths.
question_mark
Expect discussion on greedy verification within the binary search loop.
question_mark
Look for handling of edge jumps and minimal maximum logic in your solution.

warning

常见陷阱

外企场景

error
Assuming jumps can reuse stones, violating the problem constraint.
error
Failing to correctly simulate the return path, leading to underestimated jumps.
error
Mismanaging binary search bounds, which can skip the true minimal maximum.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Frog Jump with a single forward trip only, changing the binary search constraints.
arrow_right_alt
Allow revisiting stones, which changes the greedy check strategy.
arrow_right_alt
Frog Jump with variable energy limits, introducing dynamic programming options.

help

常见问题

外企场景

继续练习

#2517 礼盒的最大甜蜜度 #2528 最大化城市的最小电量 #2448 使数组相等的最小开销