双周赛做到Q2的时候我盯着“3853. 合并靠近字符”这个题名愣了几秒——字符串、相邻、合并、靠近这几个词拼在一起第一反应确实是栈但等我把规则完整读完才发现真正的坑不在“要不要用栈”而在“合并之后到底留下谁以及合并要不要循环”。这道题我在赛场上第一次提交就栽了不是因为思路方向错而是合并时少写了一层循环。这篇文章就把我的完整思考过程、代码写法、踩坑点都复盘一遍给正在备战周赛、或者想把这类“相邻消除”问题一次吃透的同学做个参考。1. 题意拆解这里的“合并”和“靠近”到底是什么意思1.1 我理解的题面题目大概是这样的给定一个只包含小写字母的字符串你可以反复执行操作——选择两个相邻的字符如果它们在字母表中的序号差不超过2就把它们合并成一个字符合并后保留其中序号较小的那个。问最终字符串的最短长度。先说“相邻”。这个约束很关键它意味着每次操作只影响局部的一对字符不会像并查集那样一下子就改变整个集合的关系。再说“靠近”两个字符的距离用它们在字母表里的位置差来衡量比如a和c序号差是2属于“靠近”可以合并a和d序号差是3就不行。最后是“合并后保留较小者”这一条直接决定了合并的方向也是我后来写错循环的根源。1.2 “靠近”是一个阈值而不是等价关系很多同学以前做过类似“删除相邻相同字符”的题目那道题里合并的条件是s[i] s[i 1]本质上是判断两个字符是否相等。这道题换成“靠近”情况立刻不一样了字符串里可能没有一对完全相同的字符但依然能一路合并到很短。我随手列了几个例子相邻字符序号差能否合并合并结果取较小a, b1可以ab, a1可以aa, c2可以ac, a2可以aa, d3不可以保持不变阈值是2意味着两个字符之间最多只能隔着一个小写字母。这样的设计让问题变得稍微有层次字符串不是“相等才能消除”而是“接近就能融合”。1.3 合并后保留较小者这个规则影响很大为什么不是随便合并也不是保留靠右边的因为保留小字符会让结果更容易继续参与后续合并。字符在字典序上越小它和左边、右边字符的“距离”往往更有可能小于等于2于是它能一路向左吞并也可能被右边更小的字符继续取代。换句话说每次合并后产生的那个“存活者”必须立刻重新检查它和左侧新邻居的关系不能只看一眼就收工。这里有一个特别容易犯的错误很多解法里遇到可以合并的相邻字符就弹出栈顶、压入新字符然后直接处理下一个字符。但这忽略了新字符可能和新的栈顶仍然满足合并条件。比如cba先处理b和a合并成a之后a还要继续和左边的c比较因为c和a的序号差也是2同样可以合并。如果不写while第一次合并完就直接跳过答案就会多出1个字符。2. 从朴素模拟到栈一条自然但不平庸的思考路径2.1 为什么不能直接暴力模拟最直观的做法是每次从头到尾扫描一遍找到第一对满足条件的相邻字符合并它们然后重新开始扫描。这个做法在字符串很短的时候没问题但字符串一长就完蛋了。假设一个字符串有n个字符每次扫描是O(n)最坏情况下每次只能合并一对一共要合并O(n)次总复杂度就是O(n^2)。如果n是10^5级别这个复杂度很可能被卡到超时。而且每次合并后字符串要重建内存复制带来的常数也很大写起来还啰嗦。所以我们应该找一个只扫描一遍、每个字符只处理常数次的方法。2.2 把“当前存活字符”维护成一条链栈的核心思想是从左到右遍历原字符串栈里保存的是“到目前为止经过若干合并之后仍然存活、且还没有和后面新字符发生关系的字符”。栈顶就是离当前扫描位置最近的存活字符。这可以类比成打砖块新读入的字符像一个新砖块滚过来它先和栈顶碰撞如果两者距离足够近就留下较小的那个然后这个“幸存者”继续往前冲和新的栈顶碰撞直到碰上一个不再满足条件的字符或者栈被撞空它才停下来作为新的栈顶入栈。这个模型天然就包含了“合并后保留较小者”的逻辑当前字符cur和栈顶比较时如果差小于等于2存活者始终是更小的那个旧的栈顶被弹出存活者继续作为新的cur。2.3 一个完整的“一路向左”的例子拿cba来走一遍读入c栈为空压入c栈变成[c]。读入b栈顶c和b差1可以合并存活者是b弹出c此时栈为空压入b栈变成[b]。读入a栈顶b和a差1可以合并存活者是a弹出b栈为空压入a栈变成[a]。最终长度是1。注意如果不写循环只做一次合并那么读入a时看到b和a合并成a就结束了栈里是[a]结果碰巧也对但这是因为这个例子只有两层。换成更长的递减串dcba只做一次合并就会出错。2.4 为什么从左到右一次扫描不会漏掉机会这里有一个直观的解释任何一次合并都发生在两个相邻字符之间而这两个字符中至少有一个在扫描过程中是“最新入栈”的角色。当右边的新字符到来时它会触发一轮向左的检查和合并这相当于把未来可能发生的相邻合并提前到了当前时刻。更严谨一点说栈算法维护了一个不变量栈中任意相邻两个字符的距离都大于2。因为只要出现距离小于等于2的相邻对while循环就会把它们合并掉。最终栈里的相邻字符距离都大于2此时字符串已经没有任何可合并的相邻对长度自然就是最短的。这个不变量也解释了为什么不需要额外处理“栈底和栈顶”这种跨距离的情况——一次合法操作只能发生在相邻位置不同时在栈里的字符之间如果距离再近也根本不相邻不可能操作。3. 核心代码实现string当栈几行就够3.1 C 实现class Solution { public: int mergeCloseCharacters(string s) { string st; for (char c : s) { char cur c; while (!st.empty() abs(st.back() - cur) 2) { cur min(st.back(), cur); st.pop_back(); } st.push_back(cur); } return st.size(); } };这段代码非常简单但每一行都有讲究。string st直接当栈用好处是最后返回st.size()就是答案而且打印调试时直接输出字符串就能看到当前存活字符序列非常直观。char cur c表示当前“活着的字符”。它一开始是新读入的字符但可能在while循环中不断被替换成更小的栈顶字符。while (!st.empty() abs(st.back() - cur) 2)是核心循环。st.back()是离当前字符最近的存活字符abs(...)计算它们的序号差。注意这里必须用while而不是if原因刚才已经说过合并后的cur可能还要继续和新的栈顶比较。cur min(st.back(), cur); st.pop_back();这两句话要连在一起理解如果栈顶更小说明合并后存活者其实是栈顶那当前的cur就被栈顶取代如果cur更小存活者还是cur。不管哪种情况旧的栈顶都不再存活必须弹出。然后把cur继续和新的栈顶比较。所有合并都完成后st.push_back(cur)把最终的存活者压栈它会在后续扫描中和其他字符继续发生关系。3.2 Python 实现class Solution: def mergeCloseCharacters(self, s: str) - int: st [] for c in s: cur c while st and abs(ord(st[-1]) - ord(cur)) 2: if st[-1] cur: cur st[-1] st.pop() st.append(cur) return len(st)Python 里字符串是不可变的所以用列表模拟栈。取字符序号时用ord()转成整数再算差比较大小则可以直接比较字符本身因为小写字母的字典序和ASCII序号顺序一致。3.3 Java 实现class Solution { public int mergeCloseCharacters(String s) { StringBuilder st new StringBuilder(); for (char c : s.toCharArray()) { char cur c; while (st.length() 0 Math.abs(st.charAt(st.length() - 1) - cur) 2) { char top st.charAt(st.length() - 1); cur (char) Math.min(top, cur); st.deleteCharAt(st.length() - 1); } st.append(cur); } return st.length(); } }Java 用StringBuilder当栈避免频繁创建新字符串。这里Math.abs(st.charAt(...) - cur)两个char相减会自动提升成int没问题。3.4 边界情况讨论空字符串循环不进st为空直接返回0。单字符串直接压栈返回1。全部字符都相同比如aaaa相邻差都是0每来一个新字符都会和栈顶合并最终栈里只剩1个a。严格递减序列比如zyxw...新字符比较小会一路往左合并最终很可能只剩一个很小的字符长度1。严格递增但距离超过2的序列比如adgj...每一步都无法合并栈会保留全部字符长度就是原长度。这些边界可以用一个for循环加几组断言快速验证我实测下来核心逻辑没有额外问题。4. 复杂度、隐藏细节与那些容易写岔的地方4.1 时间与空间复杂度每个字符在最坏情况下入栈一次、出栈一次所以总时间不是暴力模拟的O(n^2)而是O(n)。空间上最坏情况是整个字符串没有任何合并机会栈里会存下所有字符所以是O(n)在字符串处理题里属于常规水平。这里有个值得说的点虽然循环里套了while但每个字符出栈后就不会再回来所以均摊复杂度是线性的。这个套路在栈相关题目里极其常见从括号匹配到单调栈都是同一套均摊分析方法。4.2 字符距离计算的细节abs(st.back() - cur)这一步里st.back()和cur都是char直接相减会先转换成int等于字母的ASCII码之差。因为题目限定了小写字母a到z的码值是连续的所以这个差正好等于字母表序号差。我见过有人写abs(st.back() - cur) 2这是把阈值的边界搞错了。题目说的是“不超过2”所以 2才是对的。字符差为2比如a和c应当可以合并写成 2就会漏掉这一对。还有一个小坑有些编译器下char是有符号类型但对小写字母来说码值不会超过127所以不需要担心负数问题。如果题目换成扩展ASCII码或者Unicode字符这种直接相减的写法就要小心了。4.3 常见的错误写法合并一次就跳过我赛场上第一次提交写的代码大概是这样的错误版本for (char c : s) { if (!st.empty() abs(st.back() - c) 2) { st.back() min(st.back(), c); } else { st.push_back(c); } }看起来好像没问题如果栈顶和当前字符靠近就把栈顶更新成较小的那个继续读下一个字符。但问题在于当栈顶被更新成一个更小的字符后这个新栈顶和它左边的栈内元素可能又变得足够靠近了而上面的写法完全不会回头处理这种情况。比如cba读入a后栈顶从b更新成a但a和再左边的c差2可以继续合并上面的代码却直接跳到字符串末尾结果栈变成[c, a]长度错误地算成2。所以统一循环写法是必须的用一个cur变量保存“当前存活者”每次合并后都继续用这个存活者去对比新的栈顶。4.4 我竟然差点去写区间DP说实话这题我一开始没直接写栈而是怀疑它是不是要区间DP。因为题面里的“合并后保留较小者”让我想到了一类经典题两个子区间分别合并成一个字符后如果这两个字符靠近就能把整个区间合并成一个字符。这确实是区间DP的思路。但再一想区间DP的状态通常是dp[l][r][k]表示区间[l, r]能否合并成某个字符复杂度至少在O(n^3 * 字母表大小)级别Q2这个位置大概率不需要这么重的东西。而且这道题的操作只发生在相邻字符之间合并结果是两个字符中较小的一个没有“选择中间任意字符”这种灵活性所以局部贪心就是最优的。这个判断很重要先看规则里有没有“任意选择”如果有栈大概率撑不住如果规则完全确定合并结果不含选择那栈就是首选。5. 手工用例与提交复盘5.1 值得反复跑的一组用例输入合并过程输出长度a无操作1aca, c 差2合并成 a1ada, d 差3不可合并2cbab, a 合并成 ac, a 差2合并成 a1abca, b 合并成 aa, c 差2合并成 a1acea, c 合并成 aa, e 差4不可合并2dcbac, b? 一步步合并成 a1其中ace这个例子特别有意思。按“保留较小者”的规则结果是ae长度2。但如果题目改成“可以合并成区间内任意字符”那么可以先把a, c合并成c再让c, e差2继续合并成c最终长度就是1。这说明“合并规则里有没有选择空间”会彻底改变解法不能想当然。5.2 我提交时第一次错在哪我的第一次提交错误就是上面说的只合并一次用例cba直接暴露了问题。当时本地跑ac、abc都对了一交上去就发现WA整个人愣了一下然后手动模拟了cba才反应过来合并后的新字符还要继续和左边比较。第二次修改把if换成了while但同时我又犯了个小毛病while里合并后没有更新cur而是更新了st.back()然后再pop_back()再push_back()逻辑上是绕了远路虽然最后对了但代码可读性差。后来才整理成现在这种保存cur的写法。5.3 为什么这题通过率不算特别高赛后看评论区发现很多人卡住的地方其实不是栈本身而是“合并后取哪个字符”这个规则。有人误以为合并后可以任选两个字符之间的任意字母于是跑去写区间DP白白浪费时间还有人把“保留较小者”理解成“保留左边那个”在某些递减用例上会出错。这道题给我的感觉是Q2的难度不在于算法花样而在于对局部规则的精确模拟。越是这种看起来简单的题越要先在草稿纸上手推两三组数据把while循环的必要性验证明白否则很容易一上来就写出一版“看起来对但边界漏风”的代码。6. 如果题目改一改栈还成立吗6.1 变式一合并后可以取两个字符之间的任意字符假设规则改成相邻两字符差不超过2时可以把它们合并成这两个字符之间包括端点的任意一个小写字母。这时候栈贪心就可能失效了。我上面提到的ace就是一个反例。取小规则得到长度2但允许取中间字符时可以先把a, c合并成c再让c, e继续合并长度变成1。问题就在于“选择”增加了局部最优不一定等于全局最优。这种变式适合用区间可行性DP来做设dp[l][r][x]表示子串s[l..r]能否最终合并成字符x。枚举分界点k如果左半部分能合并成字符u右半部分能合并成字符v且abs(u - v) 2那么合并结果可以取u到v之间的任意字符。转移时需要遍历所有字符x判断是否落在区间内。这个DP的复杂度不低通常只适用于n很小的情况也远远超出Q2的定位。6.2 变式二阈值从2变成k如果题目把“靠近”的定义改成序号差不超过k栈做法完全不需要改变只要把 2换成 k即可。复杂度仍然是O(n)。这说明栈解法对这个“阈值”参数是高度鲁棒的因为合并规则依然是确定的保留较小者满足阈值就合并。这时候可以玩出更多测试用例。比如k很大大到25那么任意两个小写字母都算“靠近”每次合并都会保留整个字符串中的最小字符最终栈里只会剩下一个全局最小的字符。这个性质可以从栈的不变量直接推出来因为任意两字符都满足条件所有字符最终都会被合并成整个区间的最小值。6.3 变式三合并后保留较大的字符如果规则改成保留较大者代码只需要把min换成max扫描顺序可以不变。但要注意这不完全是“镜像问题”因为从左到右扫描时一个较大的“存活者”可能在后续遇到更大的字符时被替换也可能继续向右吞并小字符行为会比取小规则更依赖输入顺序。比如字符串acb取大规则下a, c先合并成c然后c, b差1合并成c长度1但如果从右往左扫c, b合并成c然后a, c合并成c结果一样。实际中确实存在一些例子不同扫描方向会得到不同结果但长度是否相同我没有严格推过这里不展开。6.4 这类“相邻消除”题型的共同套路做多了会发现这一类题目其实有一个通用判断标准操作是否只影响相邻两个元素且合并结果是否完全确定。如果答案是“是”那就可以放心用栈或者双端队列维护“当前存活序列”每个新元素触发一轮向左的合并直到不满足条件为止。如果操作结果还带有“选择空间”或者可以跨过多个元素进行区间合并那大概率要上DP至少也是区间DP级别的思考。判断这个分界点比死记硬背某个题的模板有用得多。7. 写在最后的一点体会这道题本身不难但我赛后复盘时感受最深的是周赛里很多看似复杂的题名最后解法的核心其实特别朴素。不要一上来就联想到高大上的算法先老老实实把规则翻译成代码逻辑再问自己一句“合并之后存活的字符还需要继续和其他字符比吗”这一个问题就能区分一次合并和循环合并也区分了AC和WA。另外分享一个小技巧调试这类栈问题时直接用string当栈每次循环结束打印一次st你会非常直观地看到“当前存活序列”是怎么一步步缩短的。我后来遇到所有相邻消除类题目都用这个调试方法省了不少时间。如果你拿这道题去跑更多用例会发现它还可以往很多方向扩展比如合并规则改成功率、阈值可变、合并结果允许选择每一种改动都会把问题难度抬升一个台阶。但万变不离其宗先把最基础的“栈循环合并”模型吃透后面遇到变体时再去针对性调整思路会清晰很多。