题目大意
#
给定一个整数数组 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
|