Skip to content

2498. Frog Jump II 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  int maxJump(vector<int>& stones) {
    // Let's denote the forwarding path as F and the backwarding path as B.
    // "F1 B2 B1 F2" is no better than "F1 B2 F2 B1" since the distance between
    // F1 and F2 increase, resulting a larger `ans`.
    int ans = stones[1] - stones[0];  // If there're only two stones.
    for (int i = 2; i < stones.size(); ++i)
      ans = max(ans, stones[i] - stones[i - 2]);
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public int maxJump(int[] stones) {
    // Let's denote the forwarding path as F and the backwarding path as B.
    // "F1 B2 B1 F2" is no better than "F1 B2 F2 B1" since the distance between
    // F1 and F2 increase, resulting a larger `ans`.
    int ans = stones[1] - stones[0]; // If there're only two stones.
    for (int i = 2; i < stones.length; ++i)
      ans = Math.max(ans, stones[i] - stones[i - 2]);
    return ans;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def maxJump(self, stones: List[int]) -> int:
    # Let's denote the forwarding path as F and the backwarding path as B.
    # 'F1 B2 B1 F2' is no better than 'F1 B2 F2 B1' since the distance between
    # F1 and F2 increase, resulting a larger `ans`.
    if len(stones) == 2:
      return stones[1] - stones[0]
    return max(stones[i] - stones[i - 2]
               for i in range(2, len(stones)))