Shepherd's Blog

2216. 美化数组的最少删除数

https://leetcode.cn/problems/minimum-deletions-to-make-array-beautiful/description/

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

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

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

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

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

示例 1：

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

示例 2：

1
2
3
输入：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

按照题目要求，我们只需要遍历数组，然后按照题目要求删除不满足的情况，记录下删除数字的数量。问题在于，每当我们删除一个数字后，在这个数字之后的所有部分都要向前移位，这会导致 i % 2 == 0 这个条件对于后面的数是不停变动的。既然如此，我们就从不变入手。

我们定义一个变量 tmp = -1 用它来表示当前满足 i % 2 == 0 的数，由于题目提示 0 <= nums[i] <= 105 所以我们可以将其初始化为 -1 。

  • 当 tmp == -1 时，将 tmp 更新为当前遍历值
  • 当 tmp != -1 时，判断题目条件 nums[i] != nums[i + 1]
    • 满足条件，tmp 置为 -1
    • 不满足条件，删除当前元素 ans++
  • 遍历完成后，如果 tmp != -1 则表示还有未匹配的数，返回值 - 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minDeletion(int[] nums) {
        int ans = 0;
        int tmp = -1;
        for (int i = 0; i < nums.length; i++) {
            if (tmp == -1) {
                tmp = nums[i];
            } else {
                if (tmp != nums[i]) {
                    tmp = -1;
                } else {
                    ans++;
                }
            }
        }
        return tmp == -1 ? ans : ans + 1;
    }
}
0%