Question

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.

Algorithm-1

Here, we need to consider two directions.So, in the code, we scan twice, from left to right and from right to left. The only thing needs to be careful is that, when we calculate the final answer, we can’t count the first element (0 index) and the last element because it’s never a mountain if our peak is at that position.

Code-1

C++

class Solution {
public:
    vector<int> left, right;
    void build(vector<int>& nums, int start, int end, int off, vector<int>& target) {
        vector<int> q;
        int cnt = 0;
        int i = start;
        while (i != end) {
            cnt++;
            auto it = lower_bound(q.begin(), q.end(), nums[i]);
            if (it == q.end())
                q.push_back(nums[i]);
            else
                *it = nums[i];
            target[i] = (cnt - q.size());
            i += off;
        }
    }
    int minimumMountainRemovals(vector<int>& nums) {
        int N = nums.size();
        left.resize(N);
        right.resize(N);
        build(nums, 0, N, 1, left);
        build(nums, N-1, -1, -1, right);
        int ans = N;
        for (int i=1; i<N-1; i++) {
            ans = min(ans, left[i] + right[i]);
        }
        return ans;
    }
};

Algorithm-2

给定一个数组A,问至少删除几个元素,就能得到一个”山峰数组“。思路是动态规划。枚举A[i]作为山顶,即求出以A[i]结尾的最长上升子序列的长度,和以A[i]开头的最长下降子序列的长度,两个长度加起来减去1就是以A[i]作为山顶的最长山峰数组长度。而最长上升下降子序列可以用动态规划做。 代码如下:

Code-2

Java

public class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int[] ldp = new int[nums.length], rdp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ldp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    ldp[i] = Math.max(ldp[i], ldp[j] + 1);
                }
            }
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            rdp[i] = 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    rdp[i] = Math.max(rdp[i], rdp[j] + 1);
                }
            }
        }

        int res = nums.length;
        for (int i = 1; i < nums.length - 1; i++) {
            res = Math.min(res, nums.length - ldp[i] - rdp[i] + 1);
        }

        return res;
    }
}

Java

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int length = nums.length;
        int[] prevIndices = new int[length];
        int[] nextIndices = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (stack.size() > 1 && num <= nums[stack.peek()])
                stack.pop();
            prevIndices[i] = stack.peek();
            stack.push(i);
        }
        stack = new LinkedList<Integer>();
        stack.push(length);
        for (int i = length - 1; i >= 0; i--) {
            int num = nums[i];
            while (stack.size() > 1 && num <= nums[stack.peek()])
                stack.pop();
            nextIndices[i] = stack.peek();
            stack.push(i);
        }
        int[] maxIncrease = new int[length];
        Arrays.fill(maxIncrease, 1);
        int[] maxDecrease = new int[length];
        Arrays.fill(maxDecrease, 1);
        for (int i = 0; i < length; i++) {
            if (prevIndices[i] >= 0) {
                int num = nums[i];
                for (int j = prevIndices[i]; j >= 0; j--) {
                    if (nums[j] < num)
                        maxIncrease[i] = Math.max(maxIncrease[i], maxIncrease[j] + 1);
                }
            }
        }
        for (int i = length - 1; i >= 0; i--) {
            if (nextIndices[i] < length) {
                int num = nums[i];
                for (int j = nextIndices[i]; j < length; j++) {
                    if (nums[j] < num)
                        maxDecrease[i] = Math.max(maxDecrease[i], maxDecrease[j] + 1);
                }
            }
        }
        int maxLength = 0;
        for (int i = 0; i < length; i++) {
            if (maxIncrease[i] > 1 && maxDecrease[i] > 1) {
                int curLength = maxIncrease[i] + maxDecrease[i] - 1;
                maxLength = Math.max(maxLength, curLength);
            }
        }
        return length - maxLength;
    }
}

All Problems

All Solutions