本文主要是介绍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;}
};这篇关于LeetCode 1671. 得到山形数组的最少删除次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
