LeetCode 题解工作台
美化数组的最少删除数
给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ： nums.length 为偶数 对所有满足 i % 2 == 0 的下标 i ， nums[i] != nums[i + 1] 均成立 注意，空数组同样认为是美丽数组。 你可以从 nums …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
根据题目描述，我们知道，一个美丽数组有偶数个元素，且如果我们把这个数组中每相邻两个元素划分为一组，那么每一组中的两个元素都不相等。这意味着，组内的元素不能重复，但组与组之间的元素可以重复。 因此，我们考虑从左到右遍历数组，只要遇到相邻两个元素相等，我们就将其中的一个元素删除，即删除数加一；否则，我们可以保留这两个元素。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个下标从 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 <= 1050 <= nums[i] <= 105
解题思路
方法一：贪心
根据题目描述，我们知道，一个美丽数组有偶数个元素，且如果我们把这个数组中每相邻两个元素划分为一组，那么每一组中的两个元素都不相等。这意味着，组内的元素不能重复，但组与组之间的元素可以重复。
因此，我们考虑从左到右遍历数组，只要遇到相邻两个元素相等，我们就将其中的一个元素删除，即删除数加一；否则，我们可以保留这两个元素。
最后，我们判断删除后的数组长度是否为偶数，如果不是，则说明我们需要再删除一个元素，使得最终的数组长度为偶数。
时间复杂度 ，其中 是数组的长度。我们只需要遍历数组一次。空间复杂度 。
class Solution:
def minDeletion(self, nums: List[int]) -> int:
n = len(nums)
i = ans = 0
while i < n - 1:
if nums[i] == nums[i + 1]:
ans += 1
i += 1
else:
i += 2
ans += (n - ans) % 2
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each element is processed once and stack operations are O(1). Space complexity is O(n) for the stack in the worst case when no deletions occur. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check for repeated adjacent elements violating even-odd indices.
- question_mark
Consider greedy deletions to maintain minimal operations.
- question_mark
Ask about edge cases with single-element or already beautiful arrays.
常见陷阱
外企场景- error
Forgetting to adjust the last element for even-length requirement.
- error
Deleting elements without checking parity, causing unnecessary removals.
- error
Assuming empty arrays need deletions when they are already beautiful.
进阶变体
外企场景- arrow_right_alt
Compute minimum insertions to make array beautiful instead of deletions.
- arrow_right_alt
Apply similar stack-based approach to linked lists with consecutive duplicate constraints.
- arrow_right_alt
Modify problem to require alternating increases and decreases rather than duplicates.