Skip to content

Latest commit

 

History

History
152 lines (122 loc) · 4 KB

File metadata and controls

152 lines (122 loc) · 4 KB

English Version

题目描述

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

  • arr.length >= 3
  • 存在下标 i0 < 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;
    }
}

...