使数组美丽的最小删除次数（LeetCode 2216）题解：从栈模拟到连续段压缩的 O(n) 奇偶性优化

本篇技术指南以 codeforces-go 开源仓库中 第 286 场周赛 T2 的题解文档 为主体，完整讲解「Minimum Deletions to Make Array Beautiful（力扣第 2216 题）」的贪心思路与 Go 实现。读者将掌握该题的三种递进解法（栈模拟 → 仅维护栈顶与栈大小的 O(1) 空间版本 → 按连续相同段压缩的高效版本），理解代码中「栈大小奇偶性」这一核心状态变量的来龙去脉，并学会借助仓库的测试框架验证算法正确性。

题目回顾：什么是「美丽数组」

给定整数数组 nums，一次操作可删除其中任意一个元素。目标是通过若干次删除，使数组满足：

• 数组长度为偶数；
• 对所有偶数下标 i（即第 0、2、4… 个元素），有 nums[i] == nums[i+1]，即相邻元素两两成对且相等。

满足上述条件的数组称为「美丽数组」。题目要求返回最少删除次数，原题完整描述见测试文件 b_test.go 中记录的力扣题目链接（第 286 场周赛，对应力扣题库第 2216 题）。本题在该仓库中的全部资源位于 leetcode/weekly/286/b/ 目录下，包含题解文档 b.md、源码 b.go、样例 b.txt 与测试 b_test.go。

思路一：朴素栈模拟（贪心）

题解文档 b.md 给出的第一条思路是：从左到右遍历数组，用一个栈模拟"构建美丽数组"的过程，并归纳出两条入栈规则：

• 如果当前栈大小为偶数，说明下一个入栈元素将落在偶数下标位置，此时可以随意加入元素（因为偶数下标处只要求成对，不要求与前者不同）；
• 如果当前栈大小为奇数，说明下一个入栈元素将落在奇数下标位置，它必须与其前面的元素（栈顶）配对，因此加入的元素不能和栈顶相同，否则就破坏了「成对相等」的要求。

按此规则贪心地将元素尽量入栈：遇到能入栈的元素就入栈，遇到与规则冲突的元素就删除。遍历结束后，若栈大小为奇数，说明最后一个元素没有配对成功，再移除栈顶。最终：

最少删除次数 = 数组长度 - 栈大小

这等价于「尽量多保留元素」。该贪心策略的正确性在于：偶数位可以接受任意值，所以只要当前位置允许，保留它永远不会使后续状态变差。

思路二：实际不需要栈，两个变量足矣

文档紧接着点明一个关键观察：实际不需要栈。

在整个模拟过程中，真正被用到的栈信息只有两个：

1. 栈顶元素的值（用于判断奇数位置能否入栈）；
2. 栈的大小（用于判断当前位置是偶数位还是奇数位）。

而栈顶元素的值，恰好就是"最近一次成功入栈的元素"，它在朴素模拟中就是上一个入栈的元素。因此只需维护一个布尔变量 odd 表示栈大小的奇偶性，即可完成整个模拟，空间复杂度降为 O(1)。

思路三（仓库实现）：按连续相同段压缩

仓库 b.go 的实现更进一步：不再逐个元素处理，而是把数组中连续相同的元素看成一段，按段批量计算。由于内部 for i < n && a[i] == a[start] { i++ } 与外部循环共用同一个下标 i，每个元素只被扫描一次，整体时间复杂度保持 O(n)。

func minDeletion(a []int) (ans int) {
	odd := false // 栈大小的奇偶性
	for i, n := 0, len(a); i < n; {
		start := i
		// 注意这里的 i 和外层循环的 i 是同一个变量，因此时间复杂度为 O(n)
		for i < n && a[i] == a[start] { i++ }
		l := i - start // 连续相同元素个数
		if !odd { // 只能放一个元素
			ans += l - 1
			odd = true
		} else if l == 1 {
			odd = false
		} else { // 放两个元素，栈
			ans += l - 2
		}
	}
	if odd { // 栈大小必须为偶数
		ans++
	}
	return
}

（该实现与 b.md 文档中的代码完全一致。）

关键不变量：相邻段的值必不相同

要理解这三个分支，先看一个由"按连续段切分"天然带来的不变量：相邻两段的值必然不同（若相同，它们本就是同一段）。

再结合入栈过程：凡是从 !odd 分支（偶数位放元素）或 else 分支（奇数位放两个元素）结束的段，栈顶元素一定等于该段的值。于是进入下一段时，新段的值 ≠ 上一段的值 = 栈顶，即栈顶永远不会等于新段首元素。这意味着"奇数位置遇到与栈顶相同的元素"的冲突在段间不会发生，各分支的推导因此变得非常干净。

三种情况的分支推导

设当前段为长度 l 的连续相同元素，odd 为进入该段前栈大小的奇偶性：

进入段前状态	段长 l	行为	删除数	出段后状态
odd == false（栈大小偶数）	任意 l ≥ 1	只能放 1 个元素，其余 l-1 个与栈顶相同、无法在奇数位入栈	l - 1	odd = true
odd == true（栈大小奇数）	l == 1	该元素与栈顶不同，可入栈，栈大小由奇变偶	0	odd = false
odd == true（栈大小奇数）	l ≥ 2	第 1 个入栈（栈变偶），第 2 个入栈（栈变奇），第 3 个起与栈顶相同无法入栈	l - 2	odd = true

逐分支验证如下：

• !odd 分支（l-1）：栈大小为偶数时，段内第一个元素可任意入栈；入栈后栈大小变奇数，栈顶为该段值，其余 l-1 个元素与栈顶相同、全部无法入栈，只能删除，故删除 l-1 个，状态翻转为 odd = true。
• l == 1 分支：栈大小为奇数时，由不变量可知该元素与栈顶不同，可以入栈；入栈后栈大小由奇变偶，删除 0 个，状态翻转为 odd = false。
• else 分支（l ≥ 2，删除 l-2）：栈大小为奇数时，第 1 个元素与栈顶不同，入栈后栈变偶、栈顶变为该段值；第 2 个元素此时处于偶数位，可以任意入栈，栈又变奇；第 3 个起再次与栈顶相同、无法入栈，全部删除，故删除 l-2 个，状态保持不变（odd = true）。

遍历结束后，若 odd 为真（栈大小为奇数），说明存在一个未配对的栈顶元素，按文档所述"若栈大小为奇数，则移除栈顶"，再删除 1 个，即代码末尾的 if odd { ans++ }。

复杂度与正确性

• 时间复杂度 O(n)：i 在整个过程中单调递增、不回头，每个元素恰好被扫描一次，循环体为常数开销；
• 空间复杂度 O(1)：只使用 odd、ans、start、l 等若干常量级变量，连栈都无需真正维护。

正确性由两部分构成：一是贪心入栈规则（偶数位可任意入栈、奇数位不得与栈顶相同）本身保证保留元素最多；二是连续段压缩在等价变换后与逐元素模拟结果完全一致——段内元素的命运由段长与入栈前的奇偶性唯一确定，而段间冲突被"相邻段值互异"这一不变量排除。

运行示例：对照仓库样例逐步推演

仓库 b.txt 提供了两个官方测试样例，下面手动推演以印证上述逻辑：

样例 1：[1,1,2,3,5] → 期望输出 1

• 段 [1,1]，l=2，!odd：删除 1，odd=true，栈顶为 1；
• 段 [2]，l=1，odd=true：入栈，删除 0，odd=false；
• 段 [3]，l=1，!odd：入栈，删除 0，odd=true；
• 段 [5]，l=1，odd=true：入栈，删除 0，odd=false；
• 末尾 odd 为假，无需额外删除。合计删除 1，与期望一致。

样例 2：[1,1,2,2,3,3] → 期望输出 2

• 段 [1,1]，l=2，!odd：删除 1，odd=true；
• 段 [2,2]，l=2，odd=true：入栈 2 个，删除 0，odd 保持 true；
• 段 [3,3]，l=2，odd=true：入栈 2 个，删除 0，odd 保持 true；
• 末尾 odd 为真，再删除栈顶 1 个。合计删除 2，与期望一致。

仓库测试框架：如何验证与复现

该题对应的测试代码位于 b_test.go：

func Test_b(t *testing.T) {
	targetCaseNum :=  -1
	if err := testutil.RunLeetCodeFuncWithFile(t, minDeletion, "b.txt", targetCaseNum); err != nil {
		t.Fatal(err)
	}
}

其核心是调用 RunLeetCodeFuncWithFile：该函数读取 b.txt 中的原始输入，按被测函数 minDeletion 的形参与返回值的个数对数据进行分组（本题 1 个入参 + 1 个返回值，故每 2 行一组：奇数行为输入数组、偶数行为期望输出），再交给基于反射的用例驱动框架自动执行与断言，支持 targetCaseNum 指定只跑某个用例（-1 表示最后一个用例，也即全部用例跑完后再整体验证）。同理，本场周赛的其他题目（如 a 题、c、d 题）也采用 a.go / a.txt / a_test.go 的同一组织方式，便于批量刷题与回归。

若需本地运行验证，可进入 leetcode/weekly/286/b 目录执行 go test -run Test_b（仓库为只读资源，此处仅介绍运行方式）。

小结

「使数组美丽的最小删除次数」是一道典型的"贪心 + 状态压缩"题目，其思考链值得反复咀嚼：

1. 先模拟：用栈按"偶数位随意、奇数位禁同"的规则贪心入栈，删除数 = 总长 − 栈大小；
2. 再压缩状态：发现只需栈顶值与栈大小两个信息，栈大小进一步只需一个奇偶性布尔量；
3. 最后压缩循环：按连续相同段批量处理，借助"相邻段值互异"的不变量，把每个段的命运用三个分支在 O(1) 时间内算清，得到总复杂度 O(n) / O(1) 的最优解。

这套"先正确再高效"的推导范式，在周赛与笔试的贪心题中非常通用：栈只是思考工具，最终实现往往只需寥寥几个变量，正如文档所言——"实际上不需要栈，用一个变量表示栈的奇偶性即可"。