题目描述
我们定义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
变成 山形状数组的最少删除次数。
样例
示例1
输入:nums = [1,3,1]
输出:0
解释:数组本身就是山形数组,所以我们不需要删除任何元素。
示例2
输入:nums = [2,1,1,5,6,2,3,1]
输出:3
解释:一种方法是将下标为 0,1 和 5 的元素删除,剩余元素为 [1,5,6,3,1] ,是山形数组。
示例3
输入:nums = [4,3,2,1,1,2,3,1]
输出:4
示例4
输入:nums = [1,2,3,4,4,3,2,1]
输出:1
提示
3 <= nums.length <= 1000
1 <= nums[i] <= 10^9
- 题目保证
nums
删除一些元素后一定能得到山形数组。
算法1
(最长上升子序列) $O(n^2)$
- 我们求出最长上升子序列
f1
和最长下降子序列f2
- 枚举每一个位置
i
,如果i
可能为山峰(左右都有比它小的数), 计算如果以i
为山峰所能构造出的山型数组的最大长度,更新这个最大长度. - 总数组的长度减去能形成的山型数组的最大长度,即为最小删除个数.
时间复杂度
- 由于数据范围很小,这里用朴素的求解LIS的两个for循环的方法计算出
f1
和f2
需要$O(n^2)$ - 枚举答案需要$O(n)$
- 故总的时间复杂度为 $O(n^2)$
C++ 代码
class Solution {
public:
int f1[1010], f2[1010];
int minimumMountainRemovals(vector<int>& arr) {
int n = arr.size();
for(int i = 0; i < n; i++){
f1[i] = 1;
for(int j = 0; j < i; j++){
if(arr[j] < arr[i]) f1[i] = max(f1[i], f1[j] + 1);
}
}
for(int i = n - 1; i >= 0; i--){
f2[i] = 1;
for(int j = n - 1; j > i; j--){
if(arr[j] < arr[i]) f2[i] = max(f2[i], f2[j] + 1);
}
}
int tot = 0;
for (int i = 0; i <= n; i++){
if(f1[i] > 1 && f2[i] > 1)
tot = max(tot, f1[i] + f2[i] - 1);
}
int ans = n - tot;
return ans;
}
};