845. Longest Mountain in Array

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

 

Example 1:

Input: arr = [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: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

 

Constraints:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 104

 

Follow up:

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

845. Longest Mountain in Array
struct Solution;

impl Solution {
    fn longest_mountain(a: Vec<i32>) -> i32 {
        let n = a.len();
        if n == 0 {
            return 0;
        }
        let mut left = vec![0; n];
        let mut right = vec![0; n];
        for i in 1..n {
            if a[i] > a[i - 1] {
                left[i] = left[i - 1] + 1;
            }
        }
        for i in (0..n - 1).rev() {
            if a[i] > a[i + 1] {
                right[i] = right[i + 1] + 1;
            }
        }
        let mut res = 0;
        for i in 0..n {
            if left[i] > 0 && right[i] > 0 {
                res = res.max(left[i] + right[i] + 1);
            }
        }
        res
    }
}

#[test]
fn test() {
    let a = vec![2, 1, 4, 7, 3, 2, 5];
    let res = 5;
    assert_eq!(Solution::longest_mountain(a), res);
    let a = vec![2, 2, 2];
    let res = 0;
    assert_eq!(Solution::longest_mountain(a), res);
}