845.md

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: 0 <= A.length <= 10000 0 <= A[i] <= 10000 Follow up:

Can you solve it using only one pass? Can you solve it in O(1) space?

思路

总结：
	遍历一次,记录下每一个山峰的长度,求出最大值.
使用两个指针：bottomLeft，bottomRight表示山坡的两个低端，top表示顶峰。
part1:
	bottomLeft 一直爬到顶端.特殊case: 一步都没往上爬(单边有峰 or 没有峰值比如2,2,2)
part2:
	bottomRight 从顶端走到低端.特殊case:一步都没往下走(单边有峰 or 没有峰比如2,2,2)
bottomRight - bottomLeft + 1 就是该山峰的长度。
更新bottomLeft = bottomRight

代码

func longestMountain(A []int) int {
    bottomLeft, top, bottomRight, max := 0, 0, 0, 0
    for bottomLeft < len(A) {
        for top = bottomLeft; top < len(A)-1; top++ {
            if A[top] >= A[top+1] {
                break
            } 
        }
        if top == bottomLeft  {
            bottomLeft++
            continue
        }
        for bottomRight = top; bottomRight < len(A)-1; bottomRight++ {
            if A[bottomRight] <= A[bottomRight+1] {
                break
            } 
        }
        //fmt.Println(bottomLeft, bottomRight)
        if bottomRight != top && max < bottomRight - bottomLeft + 1 {
            max = bottomRight - bottomLeft + 1
        }
        bottomLeft = bottomRight
    }
    return max
}