LeetCode1671.得到山形数组的最少删除次数（最长上升子序DPnlogn）

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i &＃43; 1] > ... > arr[arr.length - 1]


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

示例 1&＃xff1a;
输入&＃xff1a;nums &＃61; [1,3,1]
输出&＃xff1a;0
解释&＃xff1a;数组本身就是山形数组&＃xff0c;所以我们不需要删除任何元素。示例 2&＃xff1a;
输入&＃xff1a;nums &＃61; [2,1,1,5,6,2,3,1]
输出&＃xff1a;3
解释&＃xff1a;一种方法是将下标为 0&＃xff0c;1 和 5 的元素删除&＃xff0c;剩余元素为 [1,5,6,3,1] &＃xff0c;是山形数组。示例 3&＃xff1a;
输入&＃xff1a;nums &＃61; [4,3,2,1,1,2,3,1]
输出&＃xff1a;4示例 4&＃xff1a;
输入&＃xff1a;nums &＃61; [1,2,3,4,4,3,2,1]
输出&＃xff1a;1提示&＃xff1a;
3 <&＃61; nums.length <&＃61; 1000
1 <&＃61; nums[i] <&＃61; 10^9
题目保证 nums 删除一些元素后一定能得到山形数组。


来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode-cn.com/problems/minimum-number-of-removals-to-make-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权&＃xff0c;非商业转载请注明出处。

2. 解题

可以参考&＃xff1a;

动态规划应用–最长递增子序列 LeetCode 300

• 计算每个位置处的最长上升子序长度
• 正反双向计算2次
• 然后遍历每个位置&＃xff0c;计算 $min(n-l1-l2\&＃43;1)$

2.1 n^2 解法

class Solution {
public:int minimumMountainRemovals(vector<int>& nums) {int n &＃61; nums.size();vector<int> dp1(n, 1), dp2(n, 1);for(int i &＃61; 1; i < n; &＃43;&＃43;i){for(int j &＃61; i-1; j >&＃61; 0; --j){if(nums[j] < nums[i])dp1[i] &＃61; max(dp1[i], dp1[j]&＃43;1);}}for(int i &＃61; n-2; i >&＃61; 0; --i){for(int j &＃61; i&＃43;1; j < n; &＃43;&＃43;j){if(nums[j] < nums[i])dp2[i] &＃61; max(dp2[i], dp2[j]&＃43;1);}}int ans &＃61; INT_MAX;for(int i &＃61; 1; i < n-1; &＃43;&＃43;i){if(dp1[i]>1 && dp2[i]>1)ans &＃61; min(ans, n-(dp1[i]&＃43;dp2[i]-1));}return ans;}
};


444 ms 12.2 MB C&＃43;&＃43;

2.2 nlogn 解法

参考评论区&＃xff1a;Zhenghao-Liu

采用了二分查找的方法&＃xff0c;直接找到当前数字该插入的位置

直接复制过来Zhenghao-Liu大佬的代码&＃xff0c;如下&＃xff1a;

const int MAXN&＃61;1000;
int l2r[MAXN];
int r2l[MAXN];
const int INF&＃61;0x3f3f3f3f;
class Solution {
public:int minimumMountainRemovals(vector<int>& nums) {int size&＃61;nums.size();memset(l2r,0x3f,sizeof(l2r));memset(r2l,0x3f,sizeof(r2l));vector<int> vec;vec.reserve(size);for (int i&＃61;0;i<size;&＃43;&＃43;i){int cur&＃61;nums.at(i);auto pos&＃61;lower_bound(vec.begin(),vec.end(),cur);if (pos&＃61;&＃61;vec.end())vec.push_back(cur);else*pos&＃61;cur;l2r[i]&＃61;vec.size();}vec.clear();for (int i&＃61;size-1;i>&＃61;0;--i){int cur&＃61;nums.at(i);auto pos&＃61;lower_bound(vec.begin(),vec.end(),cur);if (pos&＃61;&＃61;vec.end())vec.push_back(cur);else*pos&＃61;cur;r2l[i]&＃61;vec.size();}int ans&＃61;INF;for (int i&＃61;1;i<size-1;&＃43;&＃43;i){int l&＃61;l2r[i];int r&＃61;r2l[i];if (l>1 && r>1)ans&＃61;min(ans,size-(l&＃43;r-1));}return ans;}
};


56 ms 11.9 MB C&＃43;&＃43;

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号&＃xff08;Michael阿明&＃xff09;&＃xff0c;一起加油、一起学习进步&＃xff01;