难度：★★☆☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

我们把数组 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
解释：不含 “山脉”。

提示：

0 <= A.length <= 10000
0 <= A[i] <= 10000

解答

方案1：直截了当

这道题是可以不用算法知识直接求解的。

我们首先找到所有山顶的位置，然后以山顶为基础，分别沿着左右方向下山，统计两个方向上要走的步数总和即可。

这里有几个地方需要注意：

1. 开头或结尾的元素最大时，也就是半个山的顶，不能称只为山顶，例如[1,2,3]。

2.这里定义了几个函数用于简化理解：
2.1 is_peak(index)，用于判断index位置处是否是山顶；
2.2 find_all_peaks()，找到数组中所有山顶所在位置；
2.3 get_len_of_the_moutain(index)：找到以index为山顶的山脉的长度

3. 返回时要在max函数最后加个零，原因是max函数如果接收空列表会报错。

class Solution:
    def longestMountain(self, A):
        if len(A) < 3:
            return 0

        def is_peak(index):
            return 1 <= index <= len(A) - 2 and A[index-1] < A[index] and A[index] > A[index+1]

        def find_all_peaks():
            return [index for index in range(len(A)) if is_peak(index)]

        def get_len_of_the_moutain(index):
            left = right = index
            length = 1
            while left > 0 and A[left-1] < A[left]:
                left -= 1
                length += 1
            while right < len(A) - 1 and A[right] > A[right+1]:
                right += 1
                length += 1
            return length

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

方法2：动态规划

我们可以定义两个数组dp1和dp2，维度和输入数组A保持一致，其中dp1[i]表示以下标i对应元素结尾的连续递增子数组，dp2[i]表示以下标i对应元素开头的连续递减子数组，两个数组所有位置都被初始化为1；这两个数组的前向计算是很简单的，这里不再赘述，需要注意的是，获得这两个数组之后，我们要做的工作是，找到一个位置，以该位置结尾的连续递增子数组的长度与以该位置开始的连续递减子数组的长度之和最大。

class Solution:
    def longestMountain(self, A):

        n = len(A)
        dp1 = [1] * n
        dp2 = [1] * n
        for i in range(1, n):
            if A[i] > A[i - 1]:
                dp1[i] = dp1[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if A[i] > A[i + 1]:
                dp2[i] = dp2[i + 1] + 1

        res = 0
        for i in range(1, n - 1):
            if dp1[i] > 1 and dp2[i] > 1:
                cur = dp1[i] + dp2[i] - 1
                res = max(res, cur)

        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析