⭐ 题目日期：

拼多多 - 2024/10/19

🌳 题目描述：

把符合下列属性的数组 arr 称为 山脉数组 ：

• arr.length >= 3
• 存在下标 i（0 < i < arr.length - 1），满足
• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

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

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

要找最长山脉，我们需要找到所有的山脉，返回最长的即可。

而山脉只有三种有效的形状：

而其他的皆为无效形状：

因此，我们只需要一个状态值记录当前山脉的走向，上升 1，下降 -1，无效状态 0。

上升：好判断，arr[i] > arr[i - 1]

下降：只记录由上升转下降 arr[i] < arr[i - 1] （只有这一个状态能转化为有效的下降状态），状态记为-1。平路转下降视为无效 0。

无效：遇到平路状态设为0，平路转下坡，状态依然为0，只有平路转上升，状态变为上升 1

状态设置好之后，我们只需要在三种有效山脉更新最长的山脉长度。

1. 下降转上升 - direction == -1, arr[i] > arr[i - 1]
2. 下降转平路 - direction == -1, arr[i] == arr[i - 1]
3. 一直下降直到数组访问完成 - direction == -1

返回最大值

💻代码：

Java

public int longestMountain(int[] arr) {
   if (arr == null || arr.length < 3) {
       return 0;
   }

   int max = 0;
   int left = 0;
   // 1 - 上升，-1 下降，0 无效状态
   int direction = 0;
   for (int i = 1; i < arr.length; i++) {
       if (arr[i] > arr[i - 1]) {
           if (direction == - 1) {
               max = Math.max(max, i - left);
           }
           if (direction != 1) {
               left = i - 1;
               direction = 1;
           }
       } else if (arr[i] < arr[i - 1]) {
           if (direction == 1) {
               direction = -1;
           }
       } else {
           if (direction == - 1) {
               max = Math.max(max, i - left);
           }
           direction = 0;
       }
   }

   return direction == -1 ? Math.max(max, arr.length - left) : max;
}

🚵🏻复杂度分析：

时间复杂度：O(n)

空间复杂度：O(1)

题目链接