LeetCode-longest-peak

目录隐藏

问题

Given an array arr[] with N elements, the task is to find out the longest sub-array which has the shape of a mountain.

A mountain sub-array consists of elements that are initially in ascending order until a peak element is reached and beyond the peak element all other elements of the sub-array are in decreasing order.

Input: arr = [1, 3, 1, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5]
Output: 11
Explanation:
There are two sub-arrays that can be considered as mountain sub-arrays. The first one is from index 0 – 2 (3 elements) and next one is from index 2 – 12 (11 elements). As 11 > 2, our answer is 11.

解答：

找到一个山峰，大于前一个值小于后一个值，然后向两边扩展，计算其最大值。

def longestPeak(array):
    longestPeakLength = 0
    i = 1
    while i < len(array) - 1:
        # find peak and calculate the max length
        isPeak = array[i-1] < array[i] and array[i] > array[i+1]
        if not isPeak:
            i +=1 
            continue
            
        leftIdx = i - 2
        while leftIdx >=0 and array[leftIdx] < array[leftIdx + 1]:
            leftIdx -= 1
        rightIdx = i + 2
        while rightIdx < len(array) and array[rightIdx] < array[rightIdx - 1]:
            rightIdx += 1

        currentPeakLength = rightIdx - leftIdx - 1
        longestPeakLength = max(longestPeakLength, currentPeakLength)
        i = rightIdx
    return longestPeakLength

遍历数组

如果是当前值大于等于下一个值继续不计数
如果是当前值小于下一个值，计数
如果已经到达边界或者与下一个值相等继续不计数, (这个判断只要针对，山峰之上左边部分或右边部分)
如果当前值小于后一个值计数

def longestPeak(array):
    # Write your code here.
    n = len(array) 
    longestPeakLength = 0
    i = 1
    while i < n:
        currentPeakLength = 1
        if array[i-1] >= array[i]:
            i = i + 1
            continue

        while i < n and array[i-1] < array[i]:
            i = i + 1
            currentPeakLength += 1

        if i >= n or array[i-1] == array[i]:
            continue
        
        while i < n and array[i-1] > array[i]:
            i = i + 1
            currentPeakLength += 1

        longestPeakLength = max(longestPeakLength, currentPeakLength)

    return longestPeakLength

参考及引用：

https://www.geeksforgeeks.org/longest-mountain-subarray/

https://www.algoexpert.io/questions/longest-peak

图片fromLeader Ho

LeetCode-longest-peak

问题

解答：

参考及引用：

garlic