845. Longest-Mountain-in-Array

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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

Follow up:

• Can you solve it using only one pass?

• Can you solve it in O(1) space?

Method One

class Solution {
    public int longestMountain(int[] A) {
        /*
        方法一，从左往右扫记录每个位置的连续上升长度，从右往左扫记录每个位置的连续下降长度
        在别的位置，要么只有上升，要么只有下降，要么都没有。
        唯有在山顶的位置，既有上升，又有下降，用这种办法就可以找到山顶两侧的长度。
        那么加上山顶所占的位置，山的长度就是 up[i] + down[i] + 1;
        */
        int[] up = new int[A.length];
        int[] down = new int[A.length];
        for(int i = A.length - 2; i >= 0; i--){
            if( A[i] > A[i + 1] ){
                down[i] = down[i+1] + 1;
            }
        }
        int max = 0;
        for(int i = 0; i < A.length; i++){
            if( i > 0 && A[i] > A[i - 1] ){
                up[i] = up[i - 1] + 1;
            }
            if( down[i] > 0 && up[i] > 0){
                max = Math.max( down[i] + up[i] + 1, max);
            }
        }
        return max;
    }
}
​

class Solution {
    public int longestMountain(int[] A) {
        /*
        one pass and O(1)
        的精髓在于，在一个山结束的时候 更新山的长度
        我们维护一个 up 和 down 来记录上坡和下坡的长度
        当遇到 平地 和开始新的山的时候 归零两个指针。
        */
        int up = 0;
        int down = 0;
        int max = 0;
        for(int i = 1; i < A.length; i++ ){
            if( A[i] == A[i - 1] || ( A[i] > A[i - 1]  && down > 0 )  ){
                up = 0;
                down = 0;
            }
            if( A[i] > A[i - 1]){
                up++;
            }
            if( A[i] < A[i - 1] ){
                down++;
            }
            if( up > 0 && down > 0){
                max  = Math.max( max, up + down + 1);
            }
        }
        return max;
    }
}