青蛙过河 II

标签: 贪心 数组 二分查找

难度: Medium

给你一个下标从 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 <= 105
  • 0 <= stones[i] <= 109
  • stones[0] == 0
  • stones 中的元素严格递增。

Submission

运行时间: 62 ms

内存: 30.8 MB

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

Explain

题解的核心思想是计算青蛙从第一块石头到最后一块石头并返回第一块石头的过程中遇到的最大跳跃长度。首先计算从第一块石头到第二块石头的跳跃距离，然后从第二块石头开始，计算从当前石头跳到前一块石头的距离，并用一个变量维护遇到的最大跳跃距离。这种方法确保了每次跳跃的长度是连续的两块石头之间的距离，并且通过遍历数组一次来确定最大的跳跃长度。

时间复杂度: O(n)

空间复杂度: O(1)

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

Explore

这确实是一个错误。题解中的描述与代码实现不一致。代码实际上是计算每两块石头间的距离（例如，从第 0 块石头到第 2 块，从第 1 块到第 3 块等），而不是每次从当前石头跳到前一块石头的距离。正确的实现应该是计算从一个石头到下一个石头的距离，并且，最后从最后一个石头跳回第一个石头的距离也应该被考虑进去，以确保找到真正的最大跳跃长度。

不考虑从最后一块石头跳回第一块石头的距离是一个遗漏。根据题目要求，青蛙需要从第一块石头跳到最后一块石头，然后再返回到第一块石头。因此，正确的实现应该包括计算并比较从最后一块石头跳回第一块石头的距离，这可能是整个路径中的最大跳跃距离。忽略这一点会导致算法不能正确地找到实际的最大跳跃长度。

这种一次遍历策略基于假设青蛙每次只能跳到相邻的石头或者跳过一个石头。在这种情况下，通过一次遍历数组，比较每次跳跃的长度（即相邻两块或相隔一块石头的距离），可以确保找到最大跳跃长度。这是因为数组中石头的位置是严格递增的，任何更长的跳跃都涉及更远的石头，其跳跃长度必然不会少于在它之前的任何较短跳跃。然而，这种策略还应该包括从最后一块石头跳到第一块石头的距离，以确保覆盖所有可能的跳跃情况。