【动态规划-最长递增子序列（LIS）】力扣2826. 将三个组排序

给你一个整数数组 nums 。nums 的每个元素是 1，2 或 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(vector<int>& nums) {
        int n = nums.size();
        vector<int> 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]，然后遇到x=3，替换后g=[1,2,3,5]，这时候g就是虚拟的递增子序列，因为很明显nums中没有这么一个递增子序列。接着遇到x=7，推入g，g=[1,2,3,5,7]。接着遇到x=4，替换掉g中的5，g=[1,2,3,4,7]。最后遇到x=6，替换掉了g中的最后一个元素7,g=[1,2,3,4,6]，这时候我们的最长子序列才真正变成了[1,2,3,4,6]。

知道了最长递增子序列的长度后，我们用nums的大小减去g的大小，就是我们需要删除操作的次数。

这道题可以用状态机DP来进行优化时间复杂度为O(n)

原文地址：https://blog.csdn.net/sjsjs11/article/details/142790518

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！