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) with0 < 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?
Rust Solution
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);
}
Having problems with this solution? Click here to submit an issue on github.