0845. 数组中的最长山脉

0845. 数组中的最长山脉 #

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

题目大意 #

给定一个整数数组 arr

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

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

解题思路 #

  • 使用变量 ans 保存最长山脉长度。
  • 遍历数组,假定当前节点为山峰。
  • 使用双指针 leftright 分别向左、向右查找山脉的长度。
  • 如果当前山脉的长度比最长山脉长度更长,则更新最长山脉长度。
  • 最后输出 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
本站总访问量  次  |  您是本站第  位访问者