跳至主要內容

0845. 数组中的最长山脉

ITCharge大约 1 分钟

0845. 数组中的最长山脉open in new window

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

题目链接

题目大意

描述:给定一个整数数组 arrarr

要求:返回最长山脉子数组的长度。如果不存在山脉子数组,返回 00

说明

  • 山脉数组:符合下列属性的数组 arrarr 称为山脉数组。

    • arr.length3arr.length \ge 3
    • 存在下标 i(0<i<arr.length1)i(0 < i < arr.length - 1) 满足:
      • arr[0]<arr[1]<<arr[i]arr[0] < arr[1] < … < arr[i]
      • arr[i]>arr[i+1]>>arr[arr.length1]arr[i] > arr[i + 1] > … > arr[arr.length - 1]
  • 1arr.length1041 \le arr.length \le 10^4

  • 0arr[i]1040 \le arr[i] \le 10^4

示例

  • 示例 1:
输入:arr = [2,1,4,7,3,2,5]
输出:5
解释:最长的山脉子数组是 [1,4,7,3,2],长度为 5
  • 示例 2:
输入:arr = [2,2,2]
输出:0
解释:不存在山脉子数组。

解题思路

思路 1:快慢指针

  1. 使用变量 ansans 保存最长山脉长度。
  2. 遍历数组,假定当前节点为山峰。
  3. 使用双指针 leftleftrightright 分别向左、向右查找山脉的长度。
  4. 如果当前山脉的长度比最长山脉长度更长,则更新最长山脉长度。
  5. 最后输出 ansans

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 arrarr 中的元素数量。
  • 空间复杂度O(1)O(1)