Algorithm

Problem Name: 845. Longest Mountain in Array

Problem Link: https://leetcode.com/problems/longest-mountain-in-array/
 

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

 

Example 1:

Input: arr = [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: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

 

Constraints:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 104

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int longestMountain(vector<int>& A) {
        int l = 0, r = 1, res = 0, n = A.size();
        bool up = true;
        while(r  <  n){
            if(up && r - l > 1 && A[r] < A[r - 1]) up = false;
            if(up && (A[r]  < = A[r - 1]> || !up && A[r] >= A[r - 1]){
                l = up ? r : --r;
                up = true;
            }
            r++;
            if(!up && r - l > 2) res = max(res, r - l);
        }
        return res;
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [2,1,4,7,3,2,5]

Output

x
–
+
cmd
5

#2 Code Example with Javascript Programming

Code - Javascript Programming


const longestMountain = function(A) {
        const N = A.length;
        let ans = 0, base = 0;
        while (base  <  N) {
            let end = base;
            // if base is a left-boundary
            if (end + 1 < N && A[end] < A[end + 1]) {
                // set end to the peak of this potential mountain
                while (end + 1 < N && A[end] < A[end + 1]) end++;

                // if end is really a peak..
                if (end + 1  <  N && A[end] > A[end + 1]) {
                    // set end to the right-boundary of mountain
                    while (end + 1 < N && A[end] > A[end + 1]) end++;
                    // record candidate answer
                    ans = Math.max(ans, end - base + 1);
                }
            }

            base = Math.max(end, base + 1);
        }

        return ans;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [2,1,4,7,3,2,5]

Output

x
–
+
cmd
5

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def longestMountain(self, A, res = 0):
        for i in range(1, len(A) - 1):
            if A[i + 1] < A[i] > A[i - 1]:
                l = r = i
                while l and A[l] > A[l - 1]: l -= 1
                while r + 1 < len(A) and A[r] > A[r + 1]: r += 1
                if r - l + 1 > res: res = r - l + 1
        return res
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [2,2,2]
Advertisements

Demonstration

Previous
#844 Leetcode Backspace String Compare Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#846 Leetcode Hand of Straights Solution in C, C++, Java, JavaScript, Python, C# Leetcode