requirements

We call any contiguous subarray B in array A A “mountain” that conforms to the following properties:

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

(Note: B can be any subarray of A, including the entire array A.)

Given an integer array A, return the length of the longest “mountain”.

Returns 0 if there is no “mountain”.

Example 1:

Input: [2,1,4,7,3,2,5] output: 5 explanation: the longest "mountain" is [1,4,7,3,2] and has a length of 5.Copy the code

Example 2:

Input: [2,2,2] output: 0 description: does not contain "mountains".Copy the code

The core code

class Solution:
    def longestMountain(self, arr: List[int]) - >int:
        if len(arr) < 3:
            return 0
        
        def is_peak(index) :
            return 1 <= index <=len(arr) - 2 and arr[index - 1] < arr[index] and arr[index] > arr[index + 1]
        
        def find_all_peaks() :
            return [index for index in range(len(arr)) if is_peak(index)]
        
        def get_len_of_the_moutain(index) :
            left = right = index
            length = 1
            while left > 0 and arr[left - 1] < arr[left]:
                left -= 1
                length += 1
            while right < len(arr) - 1 and arr[right] > arr[right + 1]:
                right += 1
                length += 1
            return length

        return max([get_len_of_the_moutain(peak) for peak in find_all_peaks()] + [0])  
Copy the code

Their thinking: first we will find all the possible peak points, to meet the peak point conditions is greater than the value on the left, less than the value of the right, we will all find the traverse mountain peaks, to the current peak point as the center, to the left or right to greedy search, can find out whether the length of the expansion, eventually we found a root of all the mountains of the longest.