leetcode_845 陣列中的最長山脈

要求

我們把陣列 A 中符合下列屬性的任意連續子陣列 B 稱為 “山脈”：

• B.length >= 3
• 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1] （注意：B 可以是 A 的任意子陣列，包括整個陣列 A。）

給出一個整數陣列 A，返回最長 “山脈” 的長度。

如果不含有 “山脈” 則返回 0。

示例 1： 輸入：[2,1,4,7,3,2,5] 輸出：5 解釋：最長的 “山脈” 是 [1,4,7,3,2]，長度為 5。 示例 2： 輸入：[2,2,2] 輸出：0 解釋：不含 “山脈”。

核心程式碼

```python 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])

```

解題思路：我們先將所有可能的山峰點找到，滿足山峰點的條件是大於左邊的值，小於右邊的值，我們將所有找到的山峰值進行遍歷，以當前的山峰點為中心，向左或者向右進行貪婪搜尋，看看長度是不是能擴張，最終我們在所有的山脈中找到一根最長的。