1671. Minimum Number of Removals to Make Mountain Array

Tag: monotone-stack, DP, No AC first time

Description

Solution

For each index, we can calculate its preceding minimum delete number and its succeeding delete number. Then search for the minimum sum.

So how to calculate deleting number? -> calculate longest monotonous sequence

• A naive way, use DP to calculate: Find the very nums[j] that lower than nums[i], then inherit its by length + 1

dp[i] = max(dp[j] + 1) for all nums[j] < nums[i]

• A more efficient way is to maintain a monotone-stack, and greedily replace the very nums[j] that exact greater than nums[i]. Example:

1 3 5 7 4

stack : 1 3 5 7
after : 1 3 4 7

​ So that we can maximally insert number into this monotone-stack which means can get the longest sequence.

Code

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int,int>> dp(n,{0,0});
        vector<int> stk;
        for(int i = 0; i < n; i++){
            auto pos = lower_bound(stk.begin(), stk.end(), nums[i]);
            if(pos != stk.end()){
                *pos = nums[i];
                dp[i].first = pos - stk.begin() + 1;
            }else{
                stk.push_back(nums[i]);
                dp[i].first = stk.size();
            }
        }
        while(!stk.empty()){
            stk.pop_back();
        }
        for(int i = n-1; i >= 0; i--){
            auto pos = lower_bound(stk.begin(), stk.end(), nums[i]);
            if(pos != stk.end()){
                *pos = nums[i];
                dp[i].second = pos - stk.begin() + 1;
            }else{
                stk.push_back(nums[i]);
                dp[i].second = stk.size();
            }
        }
        int res = INT_MAX;
        for(int i = 1; i < n -1; i++){
            if(dp[i].first >= 2 && dp[i].second >= 2){
                res = min(res, n - dp[i].first - dp[i].second + 1);
            }
        }
        return res;
    }
};