LeetCode 1671. 得到山形数组的最少删除次数

一、题目

1、题目描述

我们定义 arr 是 山形数组 当且仅当它满足：

• arr.length >= 3
• 存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums​ ，请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。

2、接口描述

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {

    }
};

3、原题链接

1671. 得到山形数组的最少删除次数

二、解题报告

1、思路分析

显然我们找到最长山脉子序列的长度，用原数组长度减去最长山脉子序列的长度就能得到最少删除次数。

对于山脉子序列而言，左边到山峰递增，右边到山峰也递增，那么我们正向反向都求一次最长递增子序列，找到max(pre[i] + suf[i] - 1)就是最长山脉子序列的长度

最终返回原数组长度与其的差即可

2、复杂度

时间复杂度：O(nlogn) 空间复杂度：O(n)

3、代码详解

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size() , ret = 0;
        vector<int> dp , pre(n);
        for(int i = 0 ; i < n ; i++)
        {
            if(!dp.size() || nums[i] > dp.back())
            dp.emplace_back(nums[i]) , pre[i] = dp.size();
            else
            {
                auto it = lower_bound(dp.begin() , dp.end() , nums[i]);
                *it = nums[i];
                pre[i] = it - dp.begin() + 1;
            }
        }
        dp.clear();
        for(int i = n - 1 ; i >= 0 ; i--)
        {
            if(!dp.size() || nums[i] > dp.back()){
            dp.emplace_back(nums[i]);
            if(pre[i] >= 2 && dp.size() >= 2)
                ret = max(ret , (int)dp.size() + pre[i] - 1);
            }
            else
            {
                auto it = lower_bound(dp.begin() , dp.end() , nums[i]);
                *it = nums[i];
                if(pre[i] >= 2 && (it - dp.begin() + 1) >= 2)
                    ret = max(ret , (int)(it - dp.begin()) + pre[i]);
            }
        }
        cout << ret;
        return nums.size() - ret;
    }
};