题目
来源：腾讯面经高频 —— 2025.11–2026.4 至少 4 篇面经出现，属于"一看就会、一问就漏"的那类题。
给一个只由
1~9 组成的数字串，
相邻两个数字之和为 10 就可以消除，消除后两边接在一起继续检查。问最后剩下的串是什么？（变体：求最后剩余的
最短长度。）
示例：
5512 ——
5 + 5 = 10 消除，两边接在一起得
12，
1 + 2 = 3 不能再消，答案
12。
一句话答案谁都会说：
栈模拟。但这题有三个地方能拉开差距：
- 为什么"消除后两边接在一起"用栈就自动成立？
- 消除顺序会不会影响结果？（面试官十有八九要追问）
-
"最后剩下的串"和"最短剩余长度"是同一个问题吗？
-
一、核心洞察：补数配对，把「当前串」压成一个栈
- 二、为什么栈是对的：结果唯一，所以顺序无关
- 三、动画怎么看
- 四、完整推演表
- 五、两问其实是同一问：最短长度 = 唯一约化形
- 六、实测：栈 O(n) vs 朴素重扫 O(n²)
- 七、同族题与变体
- 八、Java 版
- 九、边界与常见坑
- 十、复杂度
- 十一、面试怎么答
一、核心洞察：补数配对，把「当前串」压成一个栈
在
1~9 里，每个数字
d 的补数
10 - d 是唯一的：
两个关键事实：
- 配对是唯一的：
d 只能和 10 - d 消，没有第二种选择 —— 这是后面"结果唯一"的伏笔；
5 的补数是它自己：5 + 5 = 10，两个 5 相遇一起消失（最容易被漏掉的一格）。
题面说"消除后两边接在一起继续检查"，很多人第一反应是"删完再从头扫一遍"。
栈的视角把这件事变成一行：栈里存的就是
当前串约化后的形态，新数字进来时只看栈顶 —— 栈顶是"左边最后一个还没被消掉的数字"，它俩加起来是 10 就一起消失（栈顶弹出、新数字也不进去），否则新数字入栈。
def eliminate(s: str) -> str:
st = []
for ch in s:
if st and int(st[-1]) + int(ch) == 10:
st.pop() # 栈顶和新数字一起消失
else:
st.append(ch) # 新数字留下，成为新的栈顶
return "".join(st)
六行，
O(n)。两个容易写错的细节：
- 栈从底到顶就是答案的顺序，
"".join(st) 直接给结果，不需要反转；
- 这里用
if 就够了，不需要 while。因为一个数字最多消掉一个栈顶 —— 消掉之后它自己也消失了，不可能再跟新栈顶配对。
二、为什么栈是对的：结果唯一，所以顺序无关
栈模拟给出了
一个结果。但如果面试官问"换个消除顺序，结果会不会变"，光说"我用栈"是答不上的 —— 得证明
结果本来就是唯一的。
引理 1（终止）：每一步恰好删掉 2 个字符，串长严格递减，最多
⌊n / 2⌋ 步必然停下。
引理 2（局部合流 / 临界对）：能互相重叠的两对，只可能长成
a b a，且
a + b = 10（
b 同时是
a 的左邻和右邻）。此时"先消左边那对"和"先消右边那对"都合法，但两种消法
剩下的都是 a：
不相邻（不重叠）的两对互不干扰，谁先谁后都一样 —— 所以任何局部都是合流的。
引理 3（Newman）：一个
终止的重写系统，只要
局部合流，就
全局合流 —— 从同一个串出发，不管按什么顺序消，最后都停在
同一个不可约形上。这也解释了题面为什么能放心地问"最后剩下的串"。
于是：
"最后的串"没有歧义，"最短剩余长度"就是它。 栈模拟不是"一种可行解"，它就是那个唯一结果。
实测（tools/eliminate_sum10_bench.py）
三件事都跑过，不是空口证明：
- 穷举
1~9 上长度 ≤ 5 的全部 66430 个串：栈模拟、逐轮重扫、最左优先重扫、最右优先重扫，四种实现结果完全一致；
- 合流性实证：2000 个随机串（长度 ≤ 40）上，最左、最右、随机顺序三种消法同果；
- 不变量：栈模拟每一步的栈内容都等于"该前缀独立约化"的结果（200 个随机串逐字符核对）；结果内部一定不含相邻互补对（不可再约）。
反面教材（值得在面试里主动说）：合流性是
题目规则的功劳，不是随便什么消除规则都成立。一旦某个数字能配第二个补数，顺序就开始影响结果：
同一个串、两种消法、
两个结果 —— 这时栈模拟给出的只是某个解，不保证最优。规则一变，就得换成搜索或区间 DP。
三、动画怎么看
动画一（
algo-viz--txelim）：
栈模拟。上面是输入串，下面是栈（底 → 顶向上画）。盯三件事：
扫到哪一位（金框）、
栈顶和新数字之和是不是 10（是就一起消失，被消的栈顶留一个虚线幽灵格）、
"接在一起"的那一刻。默认输入
55128921 里，
2 + 8 消掉之后
1 和
9 紧接着消掉 —— 第二步之所以能"接上"，是因为
1 一直躺在栈里等着。
动画二（
algo-viz--txorder）：
顺序无关。同一个串
191191 上并排跑两条路线 —— A 每次消
最左边那一对，B 每次消
最右边那一对。中途形态确实不一样（A 走到
1191，B 走到
1911），但
最后都停在同一个串 11 上。更细一层：两条路线的终点虽然字符串相同，
幸存下来的是原串里不同的位置 —— A 留下下标
2 和
5，B 留下下标
0 和
3。这就是第二节那张证明表的逐帧版本。
四、完整推演表
动画一的默认输入
55128921（
n = 8）逐帧：
扫完剩
21：一共消了
3 对（
5+5、
2+8、
1+9），长度
8 - 2 × 3 = 2。第 4、5 两行是这题的灵魂：
2 + 8 消掉以后，
1 和 9 才接在一起 —— 栈什么都不用做，
1 本来就在栈里。
五、两问其实是同一问：最短长度 = 唯一约化形
"求最后剩余的
最短长度"听起来像个最优化问题，但有了第二节的引理，它就是
一个数：
- 每一步恰好删 2 个字符，所以消除次数 = (n - 结果长度) / 2 —— 次数也被结果唯一确定；
- 任何消除序列都停在同一个不可约形上（全局合流），所以不存在"更短"：那个长度就是下界，而且可达。
实测把这句也钉住了：500 个随机串、每条 6 个随机消法，
没有一条比栈结果更短。
所以被问到"最短长度"时，正确回答是"这题不存在更短，答案就是唯一约化形的长度"，而不是"我用 BFS 搜一下"。
六、实测：栈 O(n) vs 朴素重扫 O(n²)
朴素写法长这样：
每一轮从左到右删掉所有不相交的互补对，删到某一轮没有删除为止（"消除后接在一起继续检查"最直白的翻译）。
它的死穴在
对抗输入：
"1" * N + "9" * N（前半段全是
1、后半段全是
9）。整个串里
只有交界处那一对能消，消掉之后新交界又只有一对能消……于是每一轮都要
从串首扫到交界处，
N 轮下来就是
O(n²)。栈一遍扫完。
本机实测（Windows / Python 3.13.14，各项取多次最小耗时；栈在
n = 2000 时已是亚毫秒量级、接近计时噪声下限，量级为准）：
两个签名很干净：
n 翻倍，朴素耗时 4 倍起步（实测 4.1× 再 8.4×，抖动来自每轮的字符串重建与 GC），栈只在 2 倍附近摆动；- 于是差距越拉越大：
n = 2000 差 546 倍，n = 8000 已经是约 2000 倍。
栈在大
n 上的线性（同一次运行）：
顺带三个有意思的读数：
- 全是
5 时最大栈深永远是 1（两个 5 见面就消，栈里存不住第二个）；
- 随机数字串大约每 9 个字符消掉一对（实测 11.1%，
1/9 就是 11.1%）；
- 但随机串的最大栈深能到 0.78 n —— 空间最坏情况确实需要
O(n)，不能想当然说"栈里没几个"。
复现：
set PYTHONIOENCODING=utf-8 && python tools/eliminate_sum10_bench.py
# 完整输出存档：tools/eliminate_sum10_bench_output.txt
七、同族题与变体
同一台机器换个判据，就是另一道题 —— 栈不变，
"栈里存什么、怎么比"变：
判据越来越绕，骨架永远是那一句：
栈 = 当前串约化后的形态，新元素只跟栈顶发生关系。（
LC 1047 在博客另一篇
有效的括号 里也提过 —— 那道题是"配对即弹"的另一个极端。）
追问清单（面试官常用）：
- 问"一共消了多少对"：
(n - 结果长度) / 2，不用统计（见第五节）。
- 问"输出所有可能的最终串"：本题只有唯一解（引理 3），答案就是一个；规则一旦不合流（第二节的
918、991），就退化成 BFS 枚举问题。
- 问"能不能不用栈"：可以 —— 递归、或者"删一对再从头扫"都对，只是
O(n²)（实测差 2000 倍）；也可以用一个数组当栈、原地写回（把结果写回原串，只用一个游标，额外空间 O(1)）。
- 问"配对表有什么讲究"：
d ↔ 10 - d 是无重复的二对合（5 是不动点），所以每个数字只有一条出路 —— 这正是合流性的来源。把规则改成"和是 10 或 18"，9 就同时能配 1 和 9，唯一的临界对消失了，合流性跟着塌。
- 问"游戏里的消消乐 / 祖玛呢"：那是网格 + 重力 + 连锁，"相邻"是多方向的，本质仍是"消除后邻居相接"，只是"栈"变成了"扫描 + 队列"。
八、Java 版
class Solution {
public String eliminate(String s) {
Deque<Character> st = new ArrayDeque<>(); // 当栈用
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!st.isEmpty() && (st.peek() - '0') + (c - '0') == 10) {
st.pop(); // 栈顶和它一起消失
} else {
st.push(c);
}
}
StringBuilder sb = new StringBuilder();
while (!st.isEmpty()) sb.append(st.pollLast()); // 栈底 → 栈顶
return sb.toString();
}
}
两个 Java 坑：
ArrayDeque 的
push /
pop 都在
栈顶，而答案要从
栈底开始，所以取值用
pollLast()，顺着
pop() 输出会得到反串；另外别用
String 拼接来做入栈出栈 —— 那是
O(n²)，和朴素重扫一个量级。
九、边界与常见坑
- 栈空时取栈顶：
st[-1] / st.peek() 必须先判空 —— 串的第一个字符就撞在这上面。
- 只数相邻对、漏掉"接上来的"：
1289 应该全消（2+8 消掉后 1 和 9 接上再消），直接数相邻对只会消掉一对。
- 用
while 反复弹栈：不必要（一个数字最多消一个栈顶），但要能解释为什么，别背写法。
- 每轮重扫：
O(n²)，n = 8000 实测慢 2000 倍。
- 漏掉
5 + 5 = 10：5 的补数是自己；把配对表记成"1↔9、2↔8、3↔7、4↔6"就漏了 5。
- 只答"栈模拟"不证唯一性：被追问"消的顺序会不会影响结果"时答"应该不会吧"就掉档 —— 见第二节的临界对。
- 输入边界：空串、全无可消对（
12345678）、全 5、含 0 或其他字符。含 0 时它的补数是 10（不在 1~9），永远消不掉；这类输入要先跟面试官确认字符集，别自己假设。
- 输出顺序：答案是"栈底 → 栈顶"，Python 里
"".join(st) 正好，Java 里要 pollLast()。
- 把"和 10"记成"差 10"：
1 和 9 差 8 但和为 10 —— 判据是和。
十、复杂度
十一、面试怎么答
第一段 · 思路：
1~9 里每个数字的补数唯一（
d ↔ 10-d，
5 配自己），所以每个数字只有一条消法；用栈维护"当前串约化后的形态"，新数字只看栈顶 —— 互补就弹出（两者一起消失），否则入栈。"两边接在一起"是栈弹出的自然结果，不必真的去接字符串。
O(n) 时间、
O(n) 空间。
第二段 · 唯一性（
这段是区分度所在）：栈给出的不是"一种解"，而是唯一解。终止性（每步删 2 个）＋ 局部合流（唯一的临界对是
a b a，
a + b = 10，两种消法都剩
a）＋ Newman 引理 ⇒ 全局合流 ⇒ 最后的串唯一，因此"最短剩余长度"就是这个长度。顺手报个反例：规则放宽成"和是 9 或 10"，
918 会给出
8 和
9 两个结果 —— 说明合流性来自题目规则，不是普遍真理。
第三段 · 复杂度与变体：朴素"每轮重扫"是
O(n²)（对抗输入下
n = 8000 实测慢 2000 倍）；改成"相邻相同消除"是 LC 1047（LC 1209 要在栈里存
(字符, 计数)），"消
AB /
CD"是 LC 2696，"行星碰撞"是 LC 735 —— 骨架都是"栈 = 当前串的约化形"。
一句话收尾：「
栈存的是约化后的当前串，新数字只跟栈顶发生关系；这题能放心贪心，是因为它
合流 —— 顺序无关、结果唯一。」
结语
5512 这种四位串，谁都能手推出
12。真正把这题答满的是三句话：
栈 = 当前串约化后的形态（所以"两边接在一起"不用真的去接）、
两个数字能消当且仅当互补（
5 配自己别漏）、
系统合流所以结果唯一（终止 + 临界对
a b a + Newman）。第一条让你写出线性的
O(n) 代码，第二条让你不漏判据，第三条让"最短长度"这个变体不必搜索 —— 也让你在被追问"顺序会不会影响结果"时，能给出不是"应该不会"的答案。实测那一栏只是把第三条钉在数据上：
n = 8000 时朴素写法 3.5 秒，栈 1.7 毫秒，差约 2000 倍。
下一篇见。