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>& A) {
    int ans = 0;

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

      int increasing = 0;
      int decreasing = 0;

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

      while (i + 1 < A.size() && A[i] > A[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[] A) {
    int ans = 0;

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

      int increasing = 0;
      int decreasing = 0;

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

      while (i + 1 < A.length && A[i] > A[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, A: List[int]) -> int:
    ans = 0
    i = 0

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

      increasing = 0
      decreasing = 0

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

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

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

    return ans