2498.Frog Jump II
===
###### tags: `Medium`,`Array`,`Greedy`,`Binary Search`
[2498. Frog Jump II](https://leetcode.com/problems/frog-jump-ii/)
### 題目描述
You are given a **0-indexed** integer array `stones` sorted in **strictly increasing order** representing the positions of stones in a river.
A frog, initially on the first stone, wants to travel to the last stone and then return to the first stone. However, it can jump to any stone **at most once**.
The **length** of a jump is the absolute difference between the position of the stone the frog is currently on and the position of the stone to which the frog jumps.
* More formally, if the frog is at `stones[i]` and is jumping to `stones[j]`, the length of the jump is |`stones[i]` - `stones[j]`|.
The **cost** of a path is the **maximum length of a jump** among all jumps in the path.
Return *the **minimum** cost of a path for the frog*.
### 範例
**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.
```
**Constraints**:
* 2 <= `stones.length` <= 10^5^
* 0 <= `stones[i]` <= 10^9^
* `stones[0]` == 0
* `stones` is sorted in a strictly increasing order.
### 解答
#### C++
```cpp=
class Solution {
public:
int maxJump(vector<int>& stones) {
int result = stones[1];
for (int i = 2; i < stones.size(); i++) {
result = max(result, stones[i] - stones[i-2]);
}
return result;
}
};
```
> [name=Yen-Chi Chen][time=Mon, Dec 12, 2022]
#### Python
```python=
class Solution:
def maxJump(self, stones: List[int]) -> int:
return max([i - j for i, j in zip(stones[2:], stones)], default=stones[1])
```
> [name=Yen-Chi Chen][time=Mon, Dec 12, 2022]
#### Javascript
```javascript=
function maxJump(stones) {
let result = stones[1];
for (let i = 2; i < stones.length; i++) {
result = Math.max(result, stones[i] - stones[i - 2]);
}
return result;
}
```
> 吉神教學：
> 首先，跨三格沒意義，他會產生一個很大的步伐距離
> 所以問題就變成要走一步還兩步
> 然後，只要有走一步的，因為不能重複踩，回來時至少兩步以上
> 因此把所有兩步距離算出來找最大的就好
>
> 感恩彥吉讚嘆彥吉
> [name=Marsgoat][time= Dec 12, 2022]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)
Sign in with Wallet
Connect another wallet