0845. 数组中的最长山脉 #

标签：数组、双指针、动态规划、枚举
难度：中等

题目大意 #

给定一个整数数组 arr。

要求：返回最长「山脉」长度。如果不含有「山脉」则返回 0。

山脉：数组arr 中满足 arr[i - a] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[i + b] 的连续子数组。

解题思路 #

使用变量 ans 保存最长山脉长度。
遍历数组，假定当前节点为山峰。
使用双指针 left、right 分别向左、向右查找山脉的长度。
如果当前山脉的长度比最长山脉长度更长，则更新最长山脉长度。
最后输出 ans。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        size = len(arr)
        res = 0
        for i in range(1, size - 1):
            if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
                left = i - 1
                right = i + 1

                while left > 0 and arr[left - 1] < arr[left]:
                    left -= 1
                while right < size - 1 and arr[right + 1] < arr[right]:
                    right += 1
                if right - left + 1 > res:
                    res = right - left + 1
        return res