题目描述：

LeetCode 845. Longest Mountain in Array

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

• B.length >= 3
• There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain. 

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

1. 0 <= A.length <= 10000
2. 0 <= A[i] <= 10000

题目大意：

求数组中的最长“山峰”的长度

“山峰”的定义为：存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

解题思路：

分别从左往右、从右往左遍历数组

辅助数组left记录某数字左侧的最长递增子串的长度

辅助数组right记录数字右侧的最长递减子串的长度

Python代码：

class Solution(object):
    def longestMountain(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        SA = len(A)
        left, right = [0] * SA, [0] * SA
        for x in range(1, SA):
            if A[x] > A[x - 1]:
                left[x] = left[x - 1] + 1
        ans = 0
        for x in range(SA - 2, -1, -1):
            if A[x] > A[x + 1]:
                right[x] = right[x + 1] + 1
            if left[x] and right[x]:
                ans = max(ans, left[x] + right[x] + 1)
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/06/03/leetcode-longest-mountain-in-array/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码