【数据结构-邻项消除】力扣2216. 美化数组的最少删除数

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：

nums.length 为偶数
对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立
注意，空数组同样认为是美丽数组。

你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。

返回使 nums 变为美丽数组所需删除的 最少 元素数目。

示例 1：
输入：nums = [1,1,2,3,5]
输出：1
解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。

示例 2：
输入：nums = [1,1,2,2,3,3]
输出：2
解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。

构造

class Solution {
public:
    int minDeletion(vector<int>& nums) {
        int i = 0, preNum = 0;
        for(int num : nums){
            if((i&1) == 0){
                preNum = num;
                i++;
            }else if(preNum != num){
                i++;
            }
        }
        return nums.size() - ((i&1) ? i-1 : i);
    }
};

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

力扣官方给出的解法个人觉得讲的比较难懂。我们可以采用构造最长完美数组的方式，然后通过原数组长度减去最长完美数组的长度，得到最少删除数。

我们定义一个变量i来记录在构造完美数组中的索引，当i为偶数的时候，我们就让原数组的元素为preNum，如果当i为奇数，并且nums不等于preNum的时候，那么我们可以将num放到i位置，然后我们让i++指向下一个位置。

由于i始终在最后一个元素往后一个位置，所以i的最后索引实际上就是最长完美数组的长度，并且最长完美数组要求长度是偶数，那么如果i不为偶数的话，我们就令他减1。

最后我们返回原数组长度减去完美数组长度即是删除数。