Skip to content

845. Longest Mountain in Array 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int longestMountain(vector<int>& arr) {
    int ans = 0;

    for (int i = 0; i + 1 < arr.size();) {
      while (i + 1 < arr.size() && arr[i] == arr[i + 1])
        ++i;

      int increasing = 0;
      int decreasing = 0;

      while (i + 1 < arr.size() && arr[i] < arr[i + 1]) {
        ++increasing;
        ++i;
      }

      while (i + 1 < arr.size() && arr[i] > arr[i + 1]) {
        ++decreasing;
        ++i;
      }

      if (increasing > 0 && decreasing > 0)
        ans = max(ans, increasing + decreasing + 1);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int longestMountain(int[] arr) {
    int ans = 0;

    for (int i = 0; i + 1 < arr.length;) {
      while (i + 1 < arr.length && arr[i] == arr[i + 1])
        ++i;

      int increasing = 0;
      int decreasing = 0;

      while (i + 1 < arr.length && arr[i] < arr[i + 1]) {
        ++increasing;
        ++i;
      }

      while (i + 1 < arr.length && arr[i] > arr[i + 1]) {
        ++decreasing;
        ++i;
      }

      if (increasing > 0 && decreasing > 0)
        ans = Math.max(ans, increasing + decreasing + 1);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def longestMountain(self, arr: List[int]) -> int:
    ans = 0
    i = 0

    while i + 1 < len(arr):
      while i + 1 < len(arr) and arr[i] == arr[i + 1]:
        i += 1

      increasing = 0
      decreasing = 0

      while i + 1 < len(arr) and arr[i] < arr[i + 1]:
        increasing += 1
        i += 1

      while i + 1 < len(arr) and arr[i] > arr[i + 1]:
        decreasing += 1
        i += 1

      if increasing > 0 and decreasing > 0:
        ans = max(ans, increasing + decreasing + 1)

    return ans