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
解释：不含 “山脉”。

提示：

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

解题思路

首先不难想到暴力解法，我们只需确定三个位置，分别是山脉的左边、右边和中间，那么我们就可以确定这个山脉。

所以我们可以先通过遍历找到m的位置，然后判断是不是l==m？如果是的话，我们重新寻找m。否则的话，我们寻找r。找到r后，就要判断是不是r==m，如果不是，那么此时我们找到一个山脉，我们计算山脉的长度r-l+1即可。

class Solution:
    def longestMountain(self, A: List[int]) -> int:
        res = l = r = m = 0
        n = len(A)
        while l < n:
            while m < n - 1 and A[m] < A[m+1]:
                m += 1
            if m == l:
                l += 1
                m = r = l
                continue
            r = m
            while r < n - 1 and A[r] > A[r+1]:
                r += 1
            if m != r:
                res = max(res, r - l +1)
            l = m = r
        return res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！