我很少在牛客“每日一题”里碰到这种名字比题目唬人一倍的情况。“显生之宙”第一眼还以为是某种大型模拟或者神仙动态规划结果点进去一看题面极其朴素给一个只含小写字母的字符串你每次可以选一个长度为3的连续子串如果这个子串首尾字符相同就把中间的字符删掉然后剩下的字符串自动拼接起来。反复操作直到不存在这样的三元组为止问最终字符串的长度是多少。话说回来这道题在牛客上讨论度不低很多Java选手样例全过却卡超时也有人用StringBuilder.delete写完就交结果大数据直接爆炸。这篇博文就把我对这题的理解、踩坑过程、最终提交的Java解法一起写出来尤其是为什么用栈、为什么不能用StackCharacter、以及那些看起来“没什么”却能让你WA到怀疑人生的小细节。1. 这道题到底在考什么1.1 先别被名字唬住我先把题面转述成比较直白的说法给定一个字符串s比如ababa你可以找到长度为3的连续子串aba首字符a和尾字符a相同于是删除中间的b字符串变成aaba。这时又出现了aba位置1到3再删掉中间的b变成aa。最终aa里再也找不到首尾相同的长度为3子串输出2。这个操作本质上是在不断“压缩”字符串每删一个字符长度减1直到剩余字符串不存在任何“形如xyx的长度为3子串”。注意题目不是删除整个三元组而是只删除中间那个字符这一点非常关键很多人一开始会看成“消消乐”整组消除然后写出完全不同的代码。对于abcba过程也一样先选bcb删掉中间c变成aba再删b剩aa输出2。而abc这种没有任何首尾相同的三元组直接输出3。这道题表面上是在考“字符串模拟”但仔细想想每次删除后字符串形态都在动态变化最朴素的遍历删除解法是O(n^2)的数据范围稍微给到10^5以上就必挂。它真正想考察的是两件事第一你知不知道用栈来处理这种“相邻字符动态合并/消除”的问题第二你用Java写栈的时候有没有性能和边界意识。1.2 核心考点拆解我复盘了一下这题的几个考点按重要性排个序栈的运用新字符只会影响已经处理过的那部分字符串的尾部这是典型的“栈”应用场景。连续消除的循环处理删除一个中间字符后可能立刻又形成新的可消三元组必须用while而不是if。Java 性能细节StackCharacter自带同步锁和装箱成本在牛客这种老牌OJ上容易被卡常用char[]徒手维护栈才是保命写法。IO 处理多组测试数据 总长度可能到10^6级别Scanner勉强能过但用BufferedReader会更稳。边界条件字符串长度小于3时直接返回原长度栈空间大小、数组越界条件都要分清楚。这题放在“每日一题”系列里算一个典型的“栈模拟 性能意识”综合题专门用来筛掉那些只会写暴力 or 只会调库的人。2. 解题思路为什么是栈2.1 最容易想到的暴力做法为什么会挂如果没见过这类题第一反应通常是循环扫描整个字符串找到第一个满足s[i] s[i2]的位置删除s[i1]然后从头再扫。这个思路没有错但复杂度是灾难级别的。我举个例子abababab...这种交错串每次只能删掉一个字符删除后新的三元组只会在删除位置附近产生但你用暴力扫描会从串头一路重新遍历到尾做了大量无用功。假设原串长度10^5最坏情况下字符串本身不短每一次删除都要扫一遍操作次数可能接近10^4甚至更多总计算量直接到10^9以上牛客不给你超时才怪。用 Java 的StringBuilder实现暴力时会更快一点吗不会。StringBuilder.delete(int start, int end)底层是System.arraycopy每删一个字符就要把后面所有字符整体前移。虽然底层是C语言级别的数组拷贝但次数一多照样扛不住。更别提很多人会用s s.substring(0, i) s.substring(i1)这种写法每轮新建两个String再拼一个新String内存和 CPU 全部白给。所以说这题真正需要的第一步不是“怎么模拟”而是“怎么避免在字符串上反复做删除操作”。2.2 用生活类比理解栈我习惯把这道题类比成“排队吃串串”你面前有一根签子原字符串从左往右读字符每读一个字符就往身边的小竹篮里放一个。每次放完后你看一眼竹篮最上面三个字符如果最上面那个字符和倒数第三个字符相同说明中间那个字符是“多余的肉”直接扔掉然后剩下两个相同的字符贴在一起。接着还要再检查一次竹篮顶部因为可能形成新的“多余肉”。直到竹篮顶部不再满足条件继续读下一个字符。为什么用竹篮而不是整根签子因为每次删除中间字符后会和哪些字符产生新的关系只可能发生在“被删除字符的附近”——也就是当前篮子的尾部。更左边已经被压平的部分不会再因为右侧新字符的到来而改变。这就是栈能派上用场的核心原因。如果反过来你想在原来的字符串上直接删除每次都要重新拼接牵一发而动全身。而栈天然只关心尾部删掉一个栈元素、调整栈顶指针就完成了“字符串拼接”的效果代价是O(1)。2.3 栈模拟的规则与正确性我把栈模拟的规则写成下面四步从左到右遍历原字符串的每个字符c。把c压入栈顶。检查栈顶附近三个字符如果栈长度 ≥ 3并且栈[栈顶] 栈[栈顶-2]则说明当前栈顶、倒数第二个、倒数第三个正好构成首尾相同的三元组删除倒数第二个字符也就是中间那个字符。删除后栈长度减1但栈顶字符还是刚才压入的那个c。继续回到第3步循环检查直到条件不再满足。第3步很多人会写错成if这是致命伤。看一个最典型的例子ababa。当你读到最后一个a时栈里是[a,a,b,a]此时倒数第三个a和栈顶a相同删除中间的b栈变成[a,a,a]。紧接着栈顶三个字符变成a,a,a首尾依旧相同还能再删一次中间的a最终[a,a]。如果你用if只删了一次就退出输出结果会变成3而正确答案是2。那为什么从左到右“能消就消”就是最终正确答案而不是某一种局部贪心这类三元组消除有一个隐藏性质任意一种合法删除顺序得到的最终字符串结果是唯一的。你可以理解为每次删除操作只是把一个中间字符“摘掉”保留的首尾两个相同字符会靠在一起但它们不会因此“消失”后续所有可能的消除都建立在这两个保留字符的基础上。既然无论先删哪里最终留下的字符集合和顺序都一样那从左到右用栈贪心天然就是最优解。这个结论在牛客评论区里也常被老手直接作为结论使用初看有点反直觉多写几个例子验证就能接受。3. Java 实现完整可提交代码3.1 基础版char[] 徒手维护栈先上一版最稳的写法我提交的时候就是用这个过的。import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int solve(String s) { int n s.length(); if (n 3) { return n; } char[] stack new char[n]; int top -1; for (int i 0; i n; i) { char c s.charAt(i); stack[top] c; // 注意是 while不是 if。 while (top 2 stack[top - 2] stack[top]) { // 删除中间字符把栈顶值覆盖到被删的位置然后栈顶指针下移 stack[top - 1] stack[top]; top--; } } return top 1; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int T Integer.parseInt(br.readLine().trim()); StringBuilder ans new StringBuilder(); while (T-- 0) { String s br.readLine().trim(); ans.append(solve(s)).append(\n); } System.out.print(ans); } }核心就两行stack[top - 1] stack[top]; top--;第一次看到这行的人可能会愣一下为什么删除中间字符只要把栈顶覆盖到中间位置因为stack[top]是三元组的右端它不会消失stack[top-2]是左端也不会消失中间那个stack[top-1]才是真正要被删掉的字符。删除后新的栈元素个数减少1右端字符从索引top挪到索引top-1正好覆盖了原中间字符的位置。这一步同时完成了“拼接”和“保留右端字符”两个操作时间复杂度O(1)。3.2 为什么不用 Stack 和 LinkedList很多Java新手会写StackCharacter stack new Stack();看起来更清晰甚至peek()、pop()用起来很方便。但Stack继承自Vector它的push、pop方法都带synchronized同步锁在单线程算法题里属于纯纯的性能浪费。再加上它存储的是Character对象每压入一个字符都要进行一次装箱频繁操作会带来额外的对象分配和 GC 压力。LinkedListCharacter也能当栈用addLast、removeLast方法本身不慢但每个节点都是一个对象遍历/访问中间位置时要移动指针内存占用也不小。算法题里最稳妥的容器就是裸数组char[]加上一个int top指针没有任何多余开销。牛客评测机配置一般不算强当输入总长度到10^6时容器选型和最终运行时间的差距肉眼可见。3.3 复杂度分析与实测感受时间上每个字符最多入栈一次、出栈一次被删除时本质上就是top--扔掉中间元素所以总时间复杂度严格O(n)。空间上栈数组最大不会超过原字符串长度所以空间复杂度是O(n)。我本地拿10^5的全a字符串测过这个代码几乎是瞬间跑完输出时间不到1毫秒级别。而如果用StringBuilder暴力删10^5个a会连续触发消除每删一次就要移动剩余所有字符实际跑起来可能要数秒牛客上基本就是TLE。3.4 边界用例走查我在提交前用这几个用例跑了一遍建议你也写在本地测试里输入字符串手动模拟过程最终长度a长度1无三元组1ab长度2无三元组2aaa删中间a剩aa2aaaa删一次变aaa再删一次变aa2ababa先删中间b得aaba再删中间b得aa2abcba先删c得aba再删b得aa2abc无满足条件的三元组3aaab删第一个三元组中间的a得aab无法再删3aaab这个例子很容易算错。原串aaab中唯一可删的是位置0到2的aaa删除中间的a后变成aab。aab长度为3首尾是a和b不相同无法继续操作最终长度就是3。如果你一开始觉得“三个一样的a删掉一个还剩俩然后再挨着另一个a又能删”那就掉坑里了——因为删除三个a中间那个后首尾两个a是贴在一起的但三元组要求的是相隔一个字符aa这种相邻相同字符并不会自动触发新消除。4. 常见问题与调试实录4.1 三个容易踩的坑我在反复测试和查看评论区反馈的过程中发现这题翻车最多的三个点基本都集中在实现细节上。第一个坑是while写成if。这个前面已经强调过ababa这种链式消除的用例能立刻暴露问题。如果只是用if判断一次栈里的连续消除无法触发最终答案偏大。第二个坑是删除中间字符后没有维护好栈顶的值。有些人会写成top - 2;然后以为删除了整个三元组这显然是没读懂题。题目删的是中间的字符而不是删掉整个三元组所以栈的元素个数只减少1。另一种错误写法是删除后用stack[top] \0之类的方式“清空”字符实际上根本没有必要只要top指针正确移动后面入栈的新字符自然会覆盖这些位置。第三个坑是数组开小了。有一些人喜欢把栈数组长度开成n / 2理由是“每次消除至少会减少长度所以压缩后长度一定更小”但这是错误理解。如果字符串没有任何三元组满足条件栈会一直增长到和原串一样长所以栈容量必须开n。开n/2会导致越界报错而且是运行时ArrayIndexOutOfBoundsException排查起来还挺迷惑。4.2 排查技巧小数据暴力验证如果你不确定自己的栈模拟是不是正确我推荐一个土办法写一个绝对暴力的O(n^2)递归/循环版本然后随机生成小字符串把暴力结果和栈版本结果做对比。static int brute(String s) { int len s.length(); for (int i 0; i 2 len; i) { if (s.charAt(i) s.charAt(i 2)) { String next s.substring(0, i 1) s.substring(i 2); return brute(next); } } return len; }这个版本的原理很简单从头开始找第一个满足条件的位置删掉中间字符然后递归处理新字符串。它完美模拟了“任意顺序删除后结果唯一”的性质所以用来做对拍器非常有效。我生成过几十组随机字符串长度从1到20brute和solve的结果全部一致这让我提交的时候很有底气。4.3 如果面试官改成“整组消除”怎么变通面试官很喜欢把这种题当作引子然后现场变形。最常见的改法是“如果满足条件时删除整个长度为3的子串而不是只删除中间字符怎么办”这个变体的核心思路其实类似只是删除后的栈状态不同。如果整组删除栈顶元素和倒数第三个元素相同并且还要满足中间元素也相同也就是aaa这种那么直接top - 3即可while (top 2 stack[top - 2] stack[top] stack[top - 1] stack[top]) { top - 3; }但如果只要求首尾相同就删除整个三元组比如aba直接全删那条件不变操作变成top - 3。这类变体在面试里很常见核心考点还是“栈 边界 循环检查”不会脱离这个框架。4.4 如果想统计最多能删多少次题目如果问“最多可以操作多少次”答案其实就是原串长度 - 最终栈长度。在solve函数里额外维护一个计数器每次进入while循环删除中间字符时count最后返回count就行。这个变形我建议大家都想一想一旦面试官顺口追问你能立刻反应出来会加分不少。我在实际刷题过程中还有一个体会这题如果一开始就埋头写暴力写完后跑一下大数据发现自己TLE再回头改栈整个过程虽然能学到东西但在牛客“每日一题”这种场景下你更应该在读题阶段就看穿操作的本质。每次删除都发生在栈顶附近这就是一个信号。我后来刷多了类似题养成了一个习惯看到“字符串删除某个字符后自动拼接”这种描述先默认往栈上想再看删除条件是不是只与相邻/附近字符相关。如果是十有八九是栈模拟。这个习惯帮我省了不少时间也让我在面试遇到变形题时能快速反应过来。