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 个元素。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

解法 1：贪心

如果当前数可以作为数对中的第二个数就保留，它的下一个数直接作为下一个数对中的第一个数。复杂度 \mathcal{O}(n)。

关于该贪心算法的证明见下文。

参考代码（c++）

class Solution {
public:
    int minDeletion(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i + 1 < n; i++) {
            if (nums[i] == nums[i + 1]) ans++;
            else i++;
        }
        if ((n - ans) % 2) ans++;
        return ans;
    }
};

解法 2：dp

贪心不会证，想写不敢写？我们也可以直接 dp。记 f_x 表示 x 作为数对中的第一个数时，最多保留几个数；g_x 表示 x 作为数对中的第二个数时，最多保留几个数。考虑数 x 时，有如下 dp 方程：

• f_x = \max (g_y) + 1；
• g_x = \max_{y \ne x} (f_y) + 1。

答案就是 \max (g_x)。

因此我们可以用一个变量维护 \max (g_x)，用 map + multiset 维护 \max (f_x)。复杂度 \mathcal{O}(n \log n)。

参考代码（c++）

class Solution {
public:
    int minDeletion(vector<int>& nums) {
        // 作为第二个数时，最多保留几个数
        int ans = 0;
        // 作为第一个数时，最多保留几个数
        map<int, int> mp;
        multiset<int> st;
        for (int x : nums) {
            // 剔除 x 作为第一个数的情况，以满足第二个数不能与第一个数相同
            if (mp.count(x)) st.erase(st.find(mp[x]));
            // x 作为第一个数，前一个数任意
            mp[x] = max(mp[x], ans + 1);
            // x 作为第二个数，前一个数不能是 x，我们已经从 st 里剔除了
            if (!st.empty()) ans = max(ans, *(st.rbegin()) + 1);
            // 更新 x 作为第一个数的情况
            st.insert(mp[x]);
        }
        return nums.size() - ans;
    }
};

贪心的证明

显然最佳答案中同一个数不会连续出现三次及以上，因此我们先考虑同一个数连续出现不超过两次时，贪心算法是否正确。

在该简化问题中，如果同一个数 a_i 和 a_{i + 1 连续出现两次，而且这两个数都要保留，那么 i 必须是奇数（下标从 0 开始）。如果 i 是偶数，那么我们必须从小等于 (i + 1) 的下标里删掉一个。当删除下标 j 时，原下标大于 j 的数都会受影响（原本连续出现的两个数都能保留的，结果前面删了一下，下标的奇偶性改变了）。这个影响只会让答案不优，因此为了最小化影响，我们直接删除下标 (i + 1) 就好。我们的贪心算法在简化问题中就在做这个事。

回到原问题，如果出现同一个数 a_i, a_{i + 1}, a_{i + 2}, \cdots 连续出现超过两次，当 i 是奇数时，贪心算法会删掉下标大等于 (i + 2) 的部分；当 i 是偶数时，贪心算法会删掉下标大等于 (i + 1) 的部分。其实就是把连续出现的数减到两次，以及简化问题中的操作这两个步骤结合起来一起做。因此贪心算法正确。