1671. Minimum Number of Removals to Make Mountain 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 `nums`​​​, return the minimum number of elements to remove to make `nums​​​` a mountain array.

Example 1:

```Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.
```

Example 2:

```Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].
```

Example 3:

```Input: nums = [4,3,2,1,1,2,3,1]
Output: 4
```

Example 4:

```Input: nums = [1,2,3,4,4,3,2,1]
Output: 1
```

Constraints:

• `3 <= nums.length <= 1000`
• `1 <= nums[i] <= 109`
• It is guaranteed that you can make a mountain array out of `nums`.

1671. Minimum Number of Removals to Make Mountain Array
``````struct Solution;

impl Solution {
fn minimum_mountain_removals(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut left = vec![0; n];
let mut dp: Vec<i32> = vec![];
for i in 0..n {
let x = nums[i];
let size = match dp.binary_search(&x) {
Ok(j) => j + 1,
Err(j) => {
if j == dp.len() {
dp.push(x);
} else {
dp[j] = x;
}
j + 1
}
};
left[i] = size;
}

let mut right = vec![0; n];
let mut dp: Vec<i32> = vec![];
for i in (0..n).rev() {
let x = nums[i];
let size = match dp.binary_search(&x) {
Ok(j) => j + 1,
Err(j) => {
if j == dp.len() {
dp.push(x);
} else {
dp[j] = x;
}
j + 1
}
};
right[i] = size;
}

let mut res = n;
for i in 0..n {
if left[i] != 1 && right[i] != 1 {
res = res.min(n - (left[i] + right[i] - 1));
}
}
res as i32
}
}

#[test]
fn test() {
let nums = vec![1, 3, 1];
let res = 0;
assert_eq!(Solution::minimum_mountain_removals(nums), res);
let nums = vec![2, 1, 1, 5, 6, 2, 3, 1];
let res = 3;
assert_eq!(Solution::minimum_mountain_removals(nums), res);
let nums = vec![4, 3, 2, 1, 1, 2, 3, 1];
let res = 4;
assert_eq!(Solution::minimum_mountain_removals(nums), res);
let nums = vec![1, 2, 3, 4, 4, 3, 2, 1];
let res = 1;
assert_eq!(Solution::minimum_mountain_removals(nums), res);
}
``````