leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

1671-minimum-number-of-removals-to-make-mountain-array.rs (2376B)

      1/// 1671. Minimum Number of Removals to Make Mountain Array (Hard)
      2///
      3/// You may recall that an array arr is a *mountain array* if and only if:
      4///
      5///   * arr.length >= 3
      6///   * There exists some index i (*0-indexed*) with 0 < i < arr.length - 1 such
      7///   that:
      8///       + arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
      9///       + arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
     10///
     11/// Given an integer array nums​​​, return the *minimum* number of elements to
     12/// remove to make nums​​​ a *mountain array*.
     13///
     14/// *Example 1:*
     15///
     16///   *Input:* nums = [1,3,1]
     17///   *Output:* 0
     18///   *Explanation:* The array itself is a mountain array so we do not need to
     19///   remove any elements.
     20///
     21/// *Example 2:*
     22///
     23///   *Input:* nums = [2,1,1,5,6,2,3,1]
     24///   *Output:* 3
     25///   *Explanation:* One solution is to remove the elements at indices 0, 1, and
     26///   5, making the array nums = [1,5,6,3,1].
     27///
     28/// *Constraints:*
     29///
     30///   * 3 <= nums.length <= 1000
     31///   * 1 <= nums[i] <= 109
     32///   * It is guaranteed that you can make a mountain array out of nums.
     33///
     34use leetcode::*;
     35use std::cmp::max;
     36
     37struct Solution {}
     38
     39impl Solution {
     40    pub fn minimum_mountain_removals(nums: Vec<i32>) -> i32 {
     41        assert!(nums.len() >= 3);
     42        let mut left = vec![1; nums.len()];
     43        for i in 0..nums.len() {
     44            for k in 0..i {
     45                if nums[i] > nums[k] {
     46                    left[i] = max(left[i], left[k] + 1);
     47                }
     48            }
     49        }
     50        let mut right = vec![1; nums.len()];
     51        for i in (0..nums.len()).rev() {
     52            for k in (i + 1..nums.len()).rev() {
     53                if nums[i] > nums[k] {
     54                    right[i] = max(right[i], right[k] + 1);
     55                }
     56            }
     57        }
     58        left.iter()
     59            .enumerate()
     60            .filter(|(i, v)| **v != 1 && right[*i] != 1)
     61            .map(|(i, v)| nums.len() as i32 - v - right[i] + 1)
     62            .min()
     63            .unwrap()
     64    }
     65}
     66
     67pub fn main() {
     68    println!("{:?}", Solution::minimum_mountain_removals(arg_into(1)))
     69}
     70
     71#[cfg(test)]
     72mod tests {
     73    use crate::Solution;
     74    use leetcode::vi;
     75
     76    #[test]
     77    fn test() {
     78        assert_eq!(Solution::minimum_mountain_removals(vi("[1,3,1]")), 0);
     79        assert_eq!(
     80            Solution::minimum_mountain_removals(vi("[2,1,1,5,6,2,3,1]")),
     81            3
     82        );
     83    }
     84}