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.