845. Longest Mountain in Array.md

845. Longest Mountain in Array

---

leetcode-cn Daily Challenge on October 25th, 2020.

leetcode Daily Challenge on November 16th, 2020.

---

Difficulty : Medium

Related Topics : TwoPointers

---

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

• B.length >= 3
• There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

• 0 <= A.length <= 10000
• 0 <= A[i] <= 10000

Follow up:

• Can you solve it using only one pass?
• Can you solve it in O(1) space?

---

Solution

• mine
  • Java
    • Runtime: 5 ms, faster than 11.13, Memory Usage: 40 MB, less than 6.87% of Java online submissions

      //O(N)time
      //O(1)space
      public int longestMountain(int[] A) {
          int n = A.length;
          if (n < 3) return 0;
          int res = 0, t = 1;
          // 1:up 2:down 3:same
          LinkedList<Integer> list1 = new LinkedList<>();
          LinkedList<Integer> list2 = new LinkedList<>();
          int state;
          if (A[1] > A[0]) state = 1;
          else if (A[1] < A[0]) state = 2;
          else state = 3;
          for (int i = 1; i < n; i++) {
              if (A[i] > A[i - 1] && state == 1
                      || A[i] < A[i - 1] && state == 2
                      || state == 3 && A[i] == A[i - 1]) {
                  t++;
              } else {
                  list1.add(t);
                  list2.add(state);
                  if (A[i] > A[i - 1]) state = 1;
                  else if (A[i] < A[i - 1]) state = 2;
                  else state = 3;
                  t = 2;
              }
              if (i + 1 == n) {
                  list1.add(t);
                  list2.add(state);
              }
          }
          if (list1.size() < 2) return 0;
          int preS = list2.removeFirst(), preV = list1.removeFirst();
          while (!list1.isEmpty()) {
              int curS = list2.removeFirst(), curV = list1.removeFirst();
              if (preS == 1 && curS == 2) {
                  res = Math.max(res, curV + preV - 1);
              }
              preV = curV;
              preS = curS;
          }
          return res;
      }
      

---

• the most votes

• Runtime: 2 ms, faster than 91.74%, Memory Usage: 40.1 MB, less than 6.87% of Java online submissions

  //O(N)time
  //O(N)space
  public int longestMountain(int[] A) {
      int n = A.length;
      if (n == 0) {
          return 0;
      }
      int[] left = new int[n];
      for (int i = 1; i < n; ++i) {
          left[i] = A[i - 1] < A[i] ? left[i - 1] + 1 : 0;
      }
      int[] right = new int[n];
      for (int i = n - 2; i >= 0; --i) {
          right[i] = A[i + 1] < A[i] ? right[i + 1] + 1 : 0;
      }
  
      int ans = 0;
      for (int i = 0; i < n; ++i) {
          if (left[i] > 0 && right[i] > 0) {
              ans = Math.max(ans, left[i] + right[i] + 1);
          }
      }
      return ans;
  }
  

• Runtime: 2 ms, faster than 91.74%, Memory Usage: 40 MB, less than 6.87% of Java online submissions

  //O(N)time
  //O(1)space
  public int longestMountain(int[] A) {
      int n = A.length;
      int ans = 0;
      int left = 0;
      while (left + 2 < n) {
          int right = left + 1;
          if (A[left] < A[left + 1]) {
              while (right + 1 < n && A[right] < A[right + 1]) {
                  ++right;
              }
              if (right < n - 1 && A[right] > A[right + 1]) {
                  while (right + 1 < n && A[right] > A[right + 1]) {
                      ++right;
                  }
                  ans = Math.max(ans, right - left + 1);
              } else {
                  ++right;
              }
          }
          left = right;
      }
      return ans;
  }
  

---