leecode |美化数组的最小删除个数

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
nums.length 为偶数
对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立
注意，空数组同样认为是美丽数组。

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

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

class Solution {
public:
    int minDeletion(vector& nums) {
        //注意  统计的是删除的个数，还要求删除的个数是最少的
        int ans = 0;
        stack stack_;
        for(int i = 0; i < nums.size(); ++i){
            int num = nums[i];
            if(!stack_.empty() && stack_.top() == num && stack_.size() % 2 != 0){
                ans += 1;
                continue;
            }else{
                stack_.push(num);
            }
        }
        if(stack_.size() % 2 != 0){
            ans += 1;
        }
        return ans;
    }
};

//用栈的思想 ，但是不要真的用栈，会增加开销
//还有，求的是最小删除 个数  不是 栈的大小	好好理一下，会更好理解
class Solution {
public:
    int minDeletion(vector& nums) {
        int n = 0, pre = -1, res = 0;
        for(int i = 0; i < nums.size(); ++i){
            int num = nums[i];
            if(n%2 != 0 && pre == num){
                res += 1;
                continue;
            }
            pre = num;
            n += 1;
        }
        int ans = 0;
        if(n % 2 == 0){
            ans = res;
        }else{
            ans = res + 1;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46