青蛙过河 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 tostones[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 <= 1050 <= stones[i] <= 109stones[0] == 0stonesis sorted in a strictly increasing order.
代码结果
运行时间: 62 ms, 内存: 30.8 MB
/*
思路：
1. 使用二分查找来找到最小代价。
2. 通过贪心策略检查某个代价是否可行。
3. 通过Java Stream简化代码逻辑。
*/
import java.util.Arrays;
public class Solution {
public int minCost(int[] stones) {
int left = 0, right = stones[stones.length - 1];
while (left < right) {
int mid = left + (right - left) / 2;
if (canCross(stones, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canCross(int[] stones, int maxJump) {
int[] visited = new int[stones.length];
return dfs(stones, maxJump, 0, visited);
}
private boolean dfs(int[] stones, int maxJump, int index, int[] visited) {
if (index == stones.length - 1) return true;
visited[index] = 1;
return Arrays.stream(stones)
.skip(index + 1)
.takeWhile(i -> stones[i] - stones[index] <= maxJump)
.anyMatch(i -> visited[i] == 0 && dfs(stones, maxJump, i, visited));
}
}解释
方法:
题解的核心思想是计算青蛙从第一块石头到最后一块石头并返回第一块石头的过程中遇到的最大跳跃长度。首先计算从第一块石头到第二块石头的跳跃距离，然后从第二块石头开始，计算从当前石头跳到前一块石头的距离，并用一个变量维护遇到的最大跳跃距离。这种方法确保了每次跳跃的长度是连续的两块石头之间的距离，并且通过遍历数组一次来确定最大的跳跃长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到'计算从当前石头跳到前一块石头的距离'，但代码实现似乎是计算每两块石头间的距离，请问这是否是一个错误？
▷🦆
算法在计算最大跳跃距离时，为何没有考虑从最后一块石头跳回第一块石头的距离？
▷🦆
题解中提到'通过遍历数组一次来确定最大的跳跃长度'，能否详细解释这种一次遍历的策略如何确保找到确切的最大跳跃长度？
▷