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 <= 10^5
  • 0 <= stones[i] <= 10^9
  • stones[0] == 0
  • stones 按严格升序排列。

提示：

  • 最优策略之一是跳到每一块石头。
  • 在向前跳跃时跳过一块石头，在向后跳跃时跳到那些被跳过的石头，可以最小化最大跳跃长度。

解题思路

这道题的关键在于理解青蛙的最优跳跃策略。根据题目提示，最优解是让青蛙在前进时跳过一些石头，在返回时跳到那些被跳过的石头。

核心思路：

  1. 贪心策略：青蛙从起点到终点时，跳到所有奇数索引的石头（0→1→3→5→…→n-1）
  2. 返回路径：青蛙从终点返回起点时，跳到所有偶数索引的石头（n-1→n-2→n-4→…→0）

这样安排的好处是：

  • 每块石头都被访问且仅访问一次
  • 跳跃距离被合理分散，避免了过长的跳跃

具体实现：

  • 前进时的跳跃：stones[1]-stones[0], stones[3]-stones[1], stones[5]-stones[3], …
  • 返回时的跳跃：stones[n-2]-stones[n-1], stones[n-4]-stones[n-2], …

我们只需要计算所有这些跳跃距离的最大值即可。

特殊情况处理：

  • 当只有2块石头时，青蛙必须直接跳过去再跳回来，答案是 stones[1] - stones[0]

时间复杂度：O(n)，只需要遍历一遍数组 空间复杂度：O(1)，只使用常数额外空间

代码实现

class Solution {
public:
    int maxJump(vector<int>& stones) {
        int n = stones.size();
        if (n == 2) return stones[1] - stones[0];
        
        int maxJumpLen = 0;
        
        // Forward jumps: 0 -> 1 -> 3 -> 5 -> ... -> n-1
        for (int i = 2; i < n; i += 2) {
            maxJumpLen = max(maxJumpLen, stones[i] - stones[i-2]);
        }
        
        // Backward jumps: n-1 -> n-2 -> n-4 -> ... -> 0
        for (int i = n-3; i >= 0; i -= 2) {
            maxJumpLen = max(maxJumpLen, stones[i+2] - stones[i]);
        }
        
        return maxJumpLen;
    }
};

class Solution:
    def maxJump(self, stones: List[int]) -> int:
        n = len(stones)
        if n == 2:
            return stones[1] - stones[0]
        
        max_jump_len = 0
        
        # Forward jumps: 0 -> 1 -> 3 -> 5 -> ... -> n-1
        for i in range(2, n, 2):
            max_jump_len = max(max_jump_len, stones[i] - stones[i-2])
        
        # Backward jumps: n-1 -> n-2 -> n-4 -> ... -> 0
        for i in range(n-3, -1, -2):
            max_jump_len = max(max_jump_len, stones[i+2] - stones[i])
        
        return max_jump_len

public class Solution {
    public int MaxJump(int[] stones) {
        int n = stones.Length;
        if (n == 2) return stones[1] - stones[0];
        
        int maxJumpLen = 0;
        
        // Forward jumps: 0 -> 1 -> 3 -> 5 -> ... -> n-1
        for (int i = 2; i < n; i += 2) {
            maxJumpLen = Math.Max(maxJumpLen, stones[i] - stones[i-2]);
        }
        
        // Backward jumps: n-1 -> n-2 -> n-4 -> ... -> 0
        for (int i = n-3; i >= 0; i -= 2) {
            maxJumpLen = Math.Max(maxJumpLen, stones[i+2] - stones[i]);
        }
        
        return maxJumpLen;
    }
}

var maxJump = function(stones) {
    const n = stones.length;
    if (n === 2) return stones[1] - stones[0];
    
    let maxCost = stones[1] - stones[0];
    
    for (let i = 2; i < n; i++) {
        maxCost = Math.max(maxCost, stones[i] - stones[i - 2]);
    }
    
    return maxCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 需要遍历数组一次计算所有跳跃距离
空间复杂度O(1) - 只使用常数额外空间存储最大跳跃长度

相关题目