README.md

845. 数组中的最长山脉

English Version

题目描述

把符合下列属性的数组 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 <= arr.length <= 104
• 0 <= arr[i] <= 104

 

进阶：

• 你可以仅用一趟扫描解决此问题吗？
• 你可以用 O(1) 空间解决此问题吗？

解法

Python3

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        left, right = 0, 1
        status = -1
        ans = 0
        while right < len(arr):
            if status == -1 or status == 1:
                if arr[right] == arr[right - 1]:
                    status = -1
                if status == -1:
                    if arr[right] > arr[right - 1]:
                        status = 1
                    else:
                        left = right
                if status == 1 and arr[right] < arr[right - 1]:
                    status = 2
            else:
                if arr[right] == arr[right - 1]:
                    status = -1
                    ans = max(ans, right - left)
                    left = right
                elif arr[right] > arr[right - 1]:
                    status = 1
                    ans = max(ans, right - left)
                    left = right - 1
            right += 1
        if status == 2:
            ans = max(right - left, ans)
        return ans

Java

class Solution {
    public int longestMountain(int[] arr) {
        int left = 0, right = 0;
        int ans = 0;
        int status = -1;
        while (++right < arr.length) {
            if (status == -1 || status == 1) {
                if (arr[right] == arr[right - 1]) {
                    status = -1;
                }
                if (status == -1) {
                    if (arr[right] > arr[right - 1]) {
                        status = 1;
                    } else {
                        left = right;
                    }
                }
                if (status == 1 && arr[right] < arr[right - 1]) {
                    status = 2;
                }
            } else {
                if (arr[right] > arr[right - 1]) {
                    status = 1;
                    ans = Math.max(right - left, ans);
                    left = right - 1;
                } else if (arr[right] == arr[right - 1]) {
                    status = -1;
                    ans = Math.max(right - left, ans);
                    left = right;
                }
            }
        }
        if (status == 2) {
            ans = Math.max(ans, right - left);
        }
        return ans;
    }
}

...