leetcode做题笔记2216. 美化数组的最少删除数

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

• nums.length 为偶数
• 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立

注意，空数组同样认为是美丽数组。

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

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

思路一：贪心

c++解法

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

分析：

根据美丽数组的定义，前后两个数不同的即可组成美丽数组，且数组长度为偶数，每次记录两个，当两个数不相等时放入美丽数组，得到最长数组长度

总结：

本题考察贪心思路，根据定义将不同的两个数不断放入数组，最后得到最大长度数组