工程网站模板制作教程,沈阳集团网站建设,手机网站宽度自适应,seo用什么论坛引流给你一个整数数组 nums 。nums 的每个元素是 1#xff0c;2 或 3。在每次操作中#xff0c;你可以删除 nums 中的一个元素。返回使 nums 成为 非递减 顺序所需操作数的 最小值。
示例 1#xff1a; 输入#xff1a;nums [2,1,3,2,1] 输出#xff1a;3 解释#xff1a; …给你一个整数数组 nums 。nums 的每个元素是 12 或 3。在每次操作中你可以删除 nums 中的一个元素。返回使 nums 成为 非递减 顺序所需操作数的 最小值。
示例 1 输入nums [2,1,3,2,1] 输出3 解释 其中一个最优方案是删除 nums[0]nums[2] 和 nums[3]。
示例 2 输入nums [1,3,2,1,3,3] 输出2 解释 其中一个最优方案是删除 nums[1] 和 nums[2]。
示例 3 输入nums [2,2,2,2,3,3] 输出0 解释 nums 已是非递减顺序的。
提示 1 nums.length 100 1 nums[i] 3
动态规划
class Solution {
public:int minimumOperations(vectorint nums) {int n nums.size();vectorint g;for(int x : nums){auto it ranges::upper_bound(g, x);if(it g.end()) g.push_back(x);else *it x;}return nums.size() - g.size();}
};时间复杂度O(nlogn)其中 n 为 nums 的长度。 空间复杂度O(n)。
这个采用了c的内置函数upper_bound对于每个nums元素x使用二分查找动态数组g来查找比x大且最接近x的位置然后用迭代器it指向这个位置。
如果迭代器it指向了g.end()那么就说明g中没有比x大的元素那么x就可以push到g里面来构成一个更长的虚拟递增子序列。为什么是虚拟下面我会谈到。如果it指向g中的某个位置那么就用x替换掉那个元素因为对于被替换的元素的前一个元素肯定比x要小且被替换的元素大于x所以说x与被替换元素的上一个元素的值会更加接近在构造最长递增子序列过程中我们希望在长度相同的情况下尽可能让这个虚拟序列更加接近。
为什么说g里面是个虚拟的递增子序列不是真正的子序列。因为我们在用x替换g里面的元素的时候由于x在nums中的位置肯定都要比g中所有元素都要大所以替换过去后并不会马上构成一个最长递增子序列。什么时候会构成真正的递增子序列那就是在被替换的元素是g里面最后一个元素的时候这时候虚拟的递增子序列才会变成真正的子序列。
举个例子nums [1,2,4,5,3,7,4,6] 一开始我们得到g[1,2,4,5]然后遇到x3替换后g[1,2,3,5]这时候g就是虚拟的递增子序列因为很明显nums中没有这么一个递增子序列。接着遇到x7推入gg[1,2,3,5,7]。接着遇到x4替换掉g中的5g[1,2,3,4,7]。最后遇到x6替换掉了g中的最后一个元素7,g[1,2,3,4,6]这时候我们的最长子序列才真正变成了[1,2,3,4,6]。
知道了最长递增子序列的长度后我们用nums的大小减去g的大小就是我们需要删除操作的次数。
这道题可以用状态机DP来进行优化时间复杂度为O(n)
